Dániel Marx
Orcid: 0000-0002-5686-8314Affiliations:
- CISPA Helmholtz Center for Information Security, Saarbrücken, Germany (since 2020)
- Max Planck Institute for Informatics, Saarbrücken, Germany (2019-2020)
- Hungarian Academy of Sciences, Institute for Computer Science and Control, Budapest, Hungary (2012-2019)
- Humboldt University Berlin, Department of Computer Science, Germany (2010-2011)
- Tel Aviv University, Blavatnik School of Computer Science, Israel (2009-2010)
- Budapest University of Technology and Economics, Department of Computer Science and Information Theory, Hungary (until 2009, PhD 2005)
According to our database1,
Dániel Marx
authored at least 202 papers
between 2000 and 2025.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on orcid.org
-
on cispa.de
-
on cs.bme.hu
-
on dl.acm.org
On csauthors.net:
Bibliography
2025
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs - Part I: Algorithmic Results.
ACM Trans. Algorithms, July, 2025
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.
ACM Trans. Comput. Theory, June, 2025
The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs.
CoRR, June, 2025
From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity.
CoRR, February, 2025
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances.
Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025
From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs.
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025
Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025
Multicut Problems in Almost-Planar Graphs: the Dependency of Complexity on the Demand Pattern.
Proceedings of the 33rd Annual European Symposium on Algorithms, 2025
Proceedings of the 33rd Annual European Symposium on Algorithms, 2025
2024
New Tools in Parameterized Complexity: Paths, Cuts, and Decomposition (Dagstuhl Seminar 24411).
Dagstuhl Reports, 2024
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges.
Proceedings of the 35th International Symposium on Algorithms and Computation, 2024
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024
List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs.
Proceedings of the 32nd Annual European Symposium on Algorithms, 2024
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern.
Proceedings of the 40th International Symposium on Computational Geometry, 2024
2023
Theor. Comput. Sci., November, 2023
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
2022
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs.
SIAM J. Comput., 2022
J. Comput. Syst. Sci., 2022
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).
Dagstuhl Reports, 2022
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022
Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search.
Proceedings of the 30th Annual European Symposium on Algorithms, 2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
2021
Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting.
Proceedings of the 2nd Symposium on Foundations of Responsible Computing, 2021
2020
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).
SIAM J. Comput., 2020
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs.
SIAM J. Comput., 2020
On the computational tractability of a geographic clustering problem arising in redistricting.
CoRR, 2020
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020
Proceedings of the 28th Annual European Symposium on Algorithms, 2020
Proceedings of the 28th Annual European Symposium on Algorithms, 2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction.
Proceedings of the 35th Computational Complexity Conference, 2020
Proceedings of the Treewidth, Kernels, and Algorithms, 2020
2019
Electron. Colloquium Comput. Complex., 2019
Dagstuhl Reports, 2019
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs.
Algorithmica, 2019
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019
Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019
Proceedings of the 35th International Symposium on Computational Geometry, 2019
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019
2018
Subexponential-time Algorithms for Maximum Independent Set in P<sub>t</sub>-free and Broom-free Graphs.
CoRR, 2018
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2017
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017
Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk).
Proceedings of the 20th International Conference on Database Theory, 2017
Proceedings of the 25th Annual European Symposium on Algorithms, 2017
Proceedings of the 33rd International Symposium on Computational Geometry, 2017
2016
Dagstuhl Reports, 2016
Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk).
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016
Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Proceedings of the 24th Annual European Symposium on Algorithms, 2016
Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
Proceedings of the Approximation, 2016
2015
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301).
Dagstuhl Reports, 2015
An exact characterization of tractable demand patterns for maximum disjoint path problems.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.
Proceedings of the Algorithms - ESA 2015, 2015
2014
ACM Trans. Algorithms, 2014
Dagstuhl Reports, 2014
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014
2013
ACM Trans. Algorithms, 2013
Dagstuhl Reports, 2013
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
Proceedings of the Algorithms - ESA 2013, 2013
Proceedings of the Frontiers in Algorithmics <i>and</i> Algorithmic Aspects in Information and Management, 2013
2012
J. Artif. Intell. Res., 2012
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).
Dagstuhl Reports, 2012
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012
Structure theorem and isomorphism test for graphs with excluded topological subgraphs.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012
Proceedings of the 27th Conference on Computational Complexity, 2012
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012
2011
Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension.
ACM Trans. Algorithms, 2011
SIAM J. Discret. Math., 2011
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011
Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011
2010
Int. J. Comput. Geom. Appl., 2010
Commun. ACM, 2010
Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties.
Algorithmica, 2010
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010
Proceedings of the Algorithm Theory, 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010
2009
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009
Proceedings of the Algorithms, 2009
Proceedings of the Algorithms, 2009
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009
Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009
Proceedings of the Principles and Practice of Constraint Programming, 2009
2008
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2007
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007
07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007
07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs.
Proceedings of the Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07., 2007
2006
Comput. Complex., 2006
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
2005
Oper. Res. Lett., 2005
NP-completeness of list coloring and precoloring extension on the edges of planar graphs.
J. Graph Theory, 2005
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005
Proceedings of the Algorithms, 2005
2004
Discret. Appl. Math., 2004
Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004
2003
Proceedings of the Approximation and Online Algorithms, First International Workshop, 2003
2002
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002
2000
Heuristic Algorithms for Joint Configuration of the Optical and Electrical Layer in Multi-Hop Wavelength Routing Networks.
Proceedings of the Proceedings IEEE INFOCOM 2000, 2000