List of research talks by Dániel Marx

List of publications

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

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

  3. 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

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

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

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

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

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

  9. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  31. 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.

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

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

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

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

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

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

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

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

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

  41. 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

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

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

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

  45. 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

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

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

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

  49. 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.

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

  51. 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

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

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

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

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

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

BackBack to homepage