List of research talks by Dániel Marx

List of publications

  1. Important separators and parameterized algorithms
    Update Meeting on Graph Cuts, University of Warsaw, Poland, April 9, 2013.
    Slides

  2. The k-disjoint paths problem in directed planar graphs
    Dagstuhl Seminar 13121: Bidimensional Structures: Algorithms, Combinatorics and Logic, Schloss Dagstuhl, Germany, March 21, 2013.
    Slides

  3. Algorithmic graph structure theory (tutorial)
    30th International Symposium on Theoretical Aspects of Computer Science, Kiel, Germany, February 27, 2013.
    Slides

  4. The k-disjoint paths problem in directed planar graphs
    Oberwolfach Workshop 1303: Graph Theory, Oberwolfach, Germany, January 17, 2013.
    Slides

  5. CSPs and fixed-parameter tractability
    Dagstuhl Seminar 12451: The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany, November 5, 2012.
    Slides

  6. Randomized techniques for parameterized problems
    7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Ljubljana, Slovenia, September 13, 2012.
    Slides

  7. Solving PLANAR k-TERMINAL CUT in O(nc√k) time
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Warwick, UK, July 13, 2012.
    Slides

  8. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
    39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Warwick, UK, July 13, 2012.
    Slides

  9. FPT suspects and tough customers: Open problems of Downey and Fellows
    Dagstuhl Seminar 12241: Data Reduction and Problem Kernels, Schloss Dagstuhl, Germany, June 14, 2012.
    Slides

  10. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
    44th ACM Symposium on Theory of Computing (STOC 2012), New York, NY, May 20, 2012.
    Slides

  11. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
    Graph Theory @ Georgia Tech, Atlanta, GA, May 8, 2012.
    Slides

  12. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
    2nd Bertinoro Workshop on Algorithms and Graphs, Bertinoro, Italy, December 15, 2011.
    Slides

  13. Kernelization of Packing Problems
    WorKer 2011: Workshop on Kernelization, Vienna, Austria, September 4, 2011.

  14. Clustering with local restrictions
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland, July 8, 2011.

  15. Constraint satisfaction parameterized by solution size
    38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland, July 6, 2011.

  16. Important separators and parameterized algorithms
    37th International Workshop on Graph-Theoretic Methods in Computer Science Teplá Monastery, Czech Republic, June 23, 2011.
    Slides

  17. Finding topological subgraphs is fixed-parameter tractable
    43th ACM Symposium on Theory of Computing (STOC 2011), San Jose, CA, June 7, 2011.
    Slides

  18. Finding topological subgraphs is fixed-parameter tractable
    Treewidth Workshop 2011, Bergen, Norway, May 19, 2011.
    Slides

  19. Survey of connections between approximation algorithms and parameterized complexity
    Dagstuhl Seminar 11091: Packing and Scheduling Algorithms for Information and Communication Services, Schloss Dagstuhl, Germany, February 28, 2011.
    Slides

  20. Important separators and parameterized algorithms
    Methods for Discrete Structures, Humboldt-Universität zu Berlin, Germany, February 7, 2011.
    Slides

  21. Known algorithms on graphs of bounded treewidth are probably optimal
    Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, January 24, 2011.
    Slides

  22. Fixed-parameter tractability of multicut parameterized by the size of the cutset
    Department of Computer Science, University of Maryland, College Park, MD, January 18, 2011.
    Slides

  23. Fixed-parameter tractability of multicut parameterized by the size of the cutset
    WorKer 2010: Workshop on Kernelization, Leident, The Netherlands, November 12, 2010.
    Slides

  24. What's next? Reductions other than kernelization
    WorKer 2010: Workshop on Kernelization, Leident, The Netherlands, November 9, 2010.
    Slides

  25. Fixed-parameter tractability of multicut parameterized by the size of the cutset
    Dagstuhl Seminar 10441: Exact Complexity of NP-hard Problems, Schloss Dagstuhl, Germany, November 1, 2010.

  26. Fixed Parameter Algorithms
    International Workshop on Tractability, Microsoft Research, Cambridge, UK, July 5, 2010.
    Slides

  27. Completely inapproximable monotone and antimonotone parameterized problems
    25th IEEE Conference on Computational Complexity (CCC 2010), Cambridge, MA, June 10, 2010.

  28. Tractable hypergraph properties for constraint satisfaction and conjunctive queries
    42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, June 8, 2010.

  29. Tractable hypergraph properties for constraint satisfaction and conjunctive queries
    Foundations of Computer Science Seminar, Weizmann Institute, Israel, May 16, 2010.
    Slides

  30. Important separators and parameterized algorithms
    Combinatorics Seminar, University of Haifa, Israel, May 5, 2010.

  31. Movement problems
    Computer Science Colloquium, Technion, Haifa, Israel, April 13, 2010.

  32. Treewidth reduction for constrained separation and bipartization problems
    Oberwolfach Workshop 1008: Graph Theory, Oberwolfach, Germany, February 23, 2010.

  33. Survey of connections between approximation algorithms and parameterized complexity
    Operations Research Seminar, Technion, Haifa, Israel, January 18, 2010.
    Slides

  34. Fixed parameter algorithms
    Open lectures for PhD students in computer science, University of Warsaw, Poland, January 8-9, 2010.
    Part 2: Treewidth
    Part 3: Complexity

  35. Survey of connections between approximation algorithms and parameterized complexity
    Dagstuhl Seminar 09511: Parameterized complexity and approximation algorithms, Schloss Dagstuhl, Germany, December 14, 2009.
    Slides

  36. Fixed parameter algorithms
    Open lectures for PhD students in computer science, University of Warsaw, Poland, December 12, 2009.
    Part 1: Algorithmic techniques

  37. Important separators and spiders
    Bertinoro Workshop on Algorithms and Graphs, Italy, December 8, 2009.
    Slides

  38. Combinatorial problems related to treewidth and its generalizations to hypergraphs
    Combinatorics Seminar, Tel Aviv University, Israel, November 8, 2009.

  39. Beyond fractional hypertree width
    Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany, October 26, 2009.
    Slides

  40. Structural complexity of CSPs: the role of treewidth and its generalizations
    Dagstuhl Seminar 09441: The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany, October 26, 2009.
    Slides

  41. FPT algorithmic techniques
    AGAPE'09 Spring School on Fixed Parameter and Exact Algorithms, Lozari, Corsica, France, May 25-26, 2009.
    Slides   Slides (printable)

  42. Constant ratio fixed-parameter approximation of the edge multicut problem
    6th Japanese-Hungarian Symposiumon Discrete Mathematics and Its Applications, Budapest, Hungary, May 16, 2009.

  43. Movement problems
    Max-Planck-Institut für Informatik, Saarbrücken, Germany, April 28, 2009.

  44. Improving local search using parameterized complexity
    Dagstuhl Seminar 09171: Adaptive, Output Sensitive, Online and Parameterized Algorithms, Schloss Dagstuhl, Germany, April 20, 2009.

  45. Tractable Structures for Constraint Satisfaction with Truth Tables
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg, Germany, February 26, 2009.

  46. Enumerating homomorphisms
    26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg, Germany, February 26, 2009.

  47. Improving local search using parameterized complexity
    Departament de Llenguatges i Sistemes Informètics, Universitat Politècnica de Catalunya, Barcelona, Spain, February 25, 2009.

  48. Fractional covers and constraint satisfaction.
    Rényi Institute, Budapest, Hungary, February 19, 2009.

  49. Approximating fractional hypertree width.
    Symposium on Discrete Algorithms (SODA) 2009, New York, NY, January 6, 2009.

  50. Improving local search using parameterized complexity
    Cork Constraint Computing Center, University College Cork, Ireland, December 10, 2008.
    Slides

  51. Movement problems
    CS Theory Seminar, Simon Fraser University, Vancouver, Canada BC, October 17, 2008.

  52. On tree width, bramble size, and expansion
    Fete of Combinatorics and Computer Science, Keszthely, Hungary August 13, 2008.

  53. On the hardness of losing weight
    International Colloquium on Automata, Languages and Programming (ICALP) 2008, Reykjavik, Iceland, July 10, 2008.

  54. Movement problems
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, Germany, June 11, 2008.

  55. Movement problems
    Friedrich-Schiller-Universität Jena, Germany, June 9, 2008.

  56. On the optimality of planar and geometric approximation schemes
    Foundations of Computer Science (FOCS) 2007, Providence, Rhode Island, October 22, 2007.

  57. Can you beat treewidth?
    Foundations of Computer Science (FOCS) 2007, Providence, Rhode Island, October 21, 2007.

  58. On tree width, bramble size, and expansion
    Charles University, Prague, Czech Republic, May 3, 2007.

  59. Parameterized complexity of constraint satisfaction problems.
    CS Theory Seminar, Simon Fraser University, Vancouver, Canada BC, April 19, 2007.

  60. On tree width, bramble size, and expansion
    Graduirtenkolleg: Methods for Discrete Structures, Humboldt-Universität zu Berlin, Germany, February 5, 2007.

  61. A parameterized view on matroid optimization problems.
    Algorithms and Complexity in Durham (ACiD) 2006, Durham, United Kingdom, September 19, 2006.

  62. Parameterized Complexity of Independence and Domination on Geometric Graphs.
    2nd International Workshop on Parameterized and Exact Computation (IWPEC) 2006, Zürich, Switzerland, September 14, 2006.

  63. A parameterized view on matroid optimization problems.
    International Colloquium on Automata, Languages and Programming (ICALP) 2006, Venice, Italy, July 14, 2006.
    Slides

  64. Chordal deletion is fixed-parameter tractable.
    Workshop on Graph-Theoretic Concepts in Computer Science (WG) 2006, Bergen, Norway, June 22, 2006.
    Slides

  65. Closest substring problems with small distances.
    Department of Computer Science and Operations Research, Université de Montréal, Canada, April 20, 2006.
    Slides

  66. Constraint Solving via Fractional Edge Covers.
    MathsCSP Workshop, St Anne's College, University of Oxford, March 22, 2006.
    Slides

  67. Constraint Solving via Fractional Edge Covers.
    Symposium on Discrete Algorithms (SODA) 2006, Miami, Florida, January 22, 2006.
    Slides

  68. The Closest Substring problem with small distances.
    Foundations of Computer Science (FOCS) 2005, Pittsburgh, Pennsylvania, October 23, 2005.
    Slides

  69. Efficient approximation schemes for geometric problems?
    European Symposium on Algorithms (ESA) 2005, Palma de Mallorca, Spain, October 4, 2005.
    Slides

  70. The Closest Substring problem with small distances.
    Dagstuhl Seminar 05301: Exact Algorithms and Fixed-Parameter Tractability, July 25, 2005.
    Slides

  71. Trees, tree width, hypertree width, fractional hypertree width.
    33. Berliner Algorithmen-Tag, Freie Universität Berlin, July 15, 2005.
    Slides

  72. The Closest Substring problem with small distances.
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, June 10, 2005.
    Slides

  73. Parameterized complexity of constraint satisfaction problems.
    ``Logik in der Informatik'' Seminar, Institut für Informatik, Humboldt-Universität zu Berlin, December 10, 2004.
    Slides

  74. Parameterized coloring problems on chordal graphs
    International Workshop on Parameterized and Exact Computation (IWPEC) 2004, Bergen, Norway, September 15, 2004.
    Slides

  75. Parameterized graph separation problems
    International Workshop on Parameterized and Exact Computation (IWPEC) 2004 Bergen, Norway, September 14, 2004.
    Slides

  76. Minimum sum multicoloring on the edges of planar graphs and partial k-trees.
    2nd Workshop on Approximation and Online Algorithms (WAOA) 2004. Bergen, Norway, September 14, 2004.
    Slides

  77. Precoloring extension on chordal graphs.
    Graph Theory 2004, Paris, France. July 6, 2004.
    Slides

  78. Parameterized complexity of constraint satisfaction problems.
    19th Annual IEEE Conference on Computational Complexity 2004. Amherst, Massachusetts, June 22, 2004.
    Slides

  79. Parameterized complexity of constraint satisfaction problems.
    Seminar of the Mathematical Logic Group, Mathematical Institute of the University of Freiburg. June 7, 2004.
    Slides

  80. How to get n out of the exponent? Introduction to parameterized complexity. [In Hungarian]
    Egerváry Research Group Combinatorial Optimization Seminar, Eötvös Loránd University. May 17, 2004.

  81. Parameterized complexity of constraint satisfaction problems.
    Seminar of the School of Electrical Engineering and Computer Science, University of Newcastle, Australia, March 15, 2004.
    Slides

  82. Graph coloring problems and their applications in scheduling. [In Hungarian]
    John von Neumann PhD stundents Conference, Budapest University of Technology and Economics. Budapest, Hungary, October 2, 2003.
    Slides

  83. Minimum sum multicoloring on the edges of trees.
    1st Workshop on Approximation and Online Algorithms (WAOA) 2003. Budapest, Hungary, September 17, 2003.
    Slides

  84. List edge multicoloring in bounded cyclicity graphs.
    3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Application. Tokyo, Japan, January 22, 2003.
    Slides

  85. A generalized family of packing and covering problems.
    Como workshop. Vila Olmo, Como, Italy, September 3, 2002.

  86. The complexity of tree multicolorings.
    Mathematical foundations of computer science (MFCS) 2002. Warsaw-Otwock, August 28, 2002.
    Slides

  87. Graph-theoretic problems in configuring WDM optical networks.
    University of Modena & Reggio Emilia, Italy, June, 2000,

BackBack to homepage