Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDániel Marx
Person information
- affiliation (since 2020): CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
- affiliation (2019-2020): Max Planck Institute for Informatics, Saarbrücken, Germany
- affiliation (2012-2019): Hungarian Academy of Sciences, Institute for Computer Science and Control, Budapest, Hungary
- affiliation (2010-2011): Humboldt University Berlin, Department of Computer Science, Germany
- affiliation (2009-2010): Tel Aviv University, Blavatnik School of Computer Science, Israel
- affiliation (until 2009, PhD 2005): Budapest University of Technology and Economics, Department of Computer Science and Information Theory, Hungary
- not to be confused with: Daniel Marx 0001
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2015
[b1]Marek Cygan, Fedor V. Fomin, Lukasz Kowalik
, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555
Journal Articles
- 2024
- [j90]Baris Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, Karol Wegrzycki:
Computing Generalized Convolutions Faster Than Brute Force. Algorithmica 86(1): 334-366 (2024) - [j89]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Domination and Cut Problems on Chordal Graphs with Bounded Leafage. Algorithmica 86(5): 1428-1474 (2024) - 2023
- [j88]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Parameterized complexity of multicut in weighted trees. Theor. Comput. Sci. 978: 114174 (2023) - 2022
- [j87]Alexander Göke, Dániel Marx, Matthias Mnich:
Parameterized algorithms for generalizations of Directed Feedback Vertex Set. Discret. Optim. 46: 100740 (2022) - [j86]Dániel Marx, R. B. Sandeep:
Incompressibility of H-free edge modification problems: Towards a dichotomy. J. Comput. Syst. Sci. 125: 25-58 (2022) - [j85]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs. SIAM J. Comput. 51(2): 254-289 (2022) - [j84]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput. 51(6): 1866-1930 (2022) - [j83]Dániel Marx, Michal Pilipczuk:
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. ACM Trans. Algorithms 18(2): 13:1-13:64 (2022) - 2021
- [j82]Benjamin Aram Berendsohn, László Kozma, Dániel Marx:
Finding and Counting Permutations via CSPs. Algorithmica 83(8): 2552-2577 (2021) - [j81]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM 68(3): 16:1-16:40 (2021) - [j80]Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay:
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. J. ACM 68(4): 30:1-30:26 (2021) - 2020
- [j79]Andreas Emil Feldmann, Dániel Marx:
The Parameterized Hardness of the k-Center Problem in Transportation Networks. Algorithmica 82(7): 1989-2005 (2020) - [j78]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted Directed Cuts. Algorithmica 82(8): 2135-2155 (2020) - [j77]Rajesh Hemant Chitnis, Andreas Emil Feldmann, Mohammad Taghi Hajiaghayi, Dániel Marx:
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). SIAM J. Comput. 49(2): 318-364 (2020) - [j76]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs. SIAM J. Comput. 49(6): 1291-1331 (2020) - 2019
- [j75]Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen:
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs. Algorithmica 81(2): 421-438 (2019) - [j74]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms. Algorithmica 81(10): 3890-3935 (2019) - [j73]Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich:
Routing with congestion in acyclic digraphs. Inf. Process. Lett. 151 (2019) - [j72]Dániel Marx, Virginia Vassilevska Williams, Neal E. Young:
Introduction to the Special Issue on SODA 2017. ACM Trans. Algorithms 15(2): 17:1-17:2 (2019) - 2018
- [j71]Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski:
Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. 9(2): 47-80 (2018) - [j70]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. SIAM J. Comput. 47(3): 675-702 (2018) - [j69]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal. ACM Trans. Algorithms 14(2): 13:1-13:30 (2018) - 2017
- [j68]Rajesh Chitnis, László Egri, Dániel Marx:
List H-Coloring a Graph by Removing Few Vertices. Algorithmica 78(1): 110-146 (2017) - [j67]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. Inf. Comput. 256: 62-82 (2017) - [j66]Dániel Marx, Paul D. Seymour, Paul Wollan:
Rooted grid minors. J. Comb. Theory, Ser. B 122: 428-437 (2017) - [j65]Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon:
Coloring Graphs with Constraints on Connectivity. J. Graph Theory 85(4): 814-838 (2017) - 2016
- [j64]Yixin Cao, Dániel Marx:
Chordal Editing is Fixed-Parameter Tractable. Algorithmica 75(1): 118-137 (2016) - [j63]Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström:
On Problems as Hard as CNF-SAT. ACM Trans. Algorithms 12(3): 41:1-41:24 (2016) - [j62]Stefan Kratsch, Dániel Marx, Magnus Wahlström:
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. ACM Trans. Comput. Theory 8(1): 1:1-1:28 (2016) - 2015
- [j61]Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra, Yngve Villanger:
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties. Algorithmica 72(3): 687-713 (2015) - [j60]Martin Grohe, Dániel Marx:
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. SIAM J. Comput. 44(1): 114-159 (2015) - [j59]Yixin Cao, Dániel Marx:
Interval Deletion Is Fixed-Parameter Tractable. ACM Trans. Algorithms 11(3): 21:1-21:35 (2015) - [j58]Dániel Marx, László A. Végh:
Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation. ACM Trans. Algorithms 11(4): 27:1-27:24 (2015) - [j57]Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx:
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ACM Trans. Algorithms 11(4): 28:1-28:28 (2015) - 2014
- [j56]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. Algorithmica 68(1): 41-61 (2014) - [j55]Dániel Marx, Igor Razgon:
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. SIAM J. Comput. 43(2): 355-388 (2014) - [j54]Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. SIAM J. Comput. 43(2): 573-616 (2014) - [j53]Dániel Marx, Paul Wollan:
Immersions in Highly Edge Connected Graphs. SIAM J. Discret. Math. 28(1): 503-520 (2014) - [j52]Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlen:
Exponential Time Complexity of the Permanent and the Tutte Polynomial. ACM Trans. Algorithms 10(4): 21:1-21:32 (2014) - [j51]Martin Grohe, Dániel Marx:
Constraint Solving via Fractional Edge Covers. ACM Trans. Algorithms 11(1): 4:1-4:20 (2014) - [j50]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. ACM Trans. Algorithms 11(2): 14:1-14:29 (2014) - 2013
- [j49]Dániel Marx, Ildikó Schlotter:
Cleaning Interval Graphs. Algorithmica 65(2): 275-316 (2013) - [j48]Daniel Lokshtanov, Dániel Marx:
Clustering with local restrictions. Inf. Comput. 222: 278-292 (2013) - [j47]Sylvain Guillemot, Dániel Marx:
A faster FPT algorithm for Bipartite Contraction. Inf. Process. Lett. 113(22-24): 906-912 (2013) - [j46]Dániel Marx:
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM 60(6): 42:1-42:51 (2013) - [j45]Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter:
Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1): 39-49 (2013) - [j44]Dániel Marx:
Completely inapproximable monotone and antimonotone parameterized problems. J. Comput. Syst. Sci. 79(1): 144-151 (2013) - [j43]Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. SIAM J. Comput. 42(4): 1674-1696 (2013) - [j42]Albert Atserias, Martin Grohe, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42(4): 1737-1767 (2013) - [j41]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4): 30:1-30:35 (2013) - 2012
- [j40]Dániel Marx, Ildikó Schlotter:
Obtaining a Planar Graph by Vertex Deletion. Algorithmica 62(3-4): 807-822 (2012) - [j39]David A. Cohen, Martin C. Cooper, Páidí Creed, Dániel Marx, András Z. Salamon:
The Tractability of CSP Classes Defined by Forbidden Patterns. J. Artif. Intell. Res. 45: 47-78 (2012) - [j38]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating homomorphisms. J. Comput. Syst. Sci. 78(2): 638-650 (2012) - [j37]Andrei A. Krokhin, Dániel Marx:
On the hardness of losing weight. ACM Trans. Algorithms 8(2): 19:1-19:18 (2012) - 2011
- [j36]Dániel Marx, Ildikó Schlotter:
Stable assignment with couples: Parameterized complexity and local search. Discret. Optim. 8(1): 25-40 (2011) - [j35]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Lower bounds based on the Exponential Time Hypothesis. Bull. EATCS 105: 41-72 (2011) - [j34]MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx:
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM 58(5): 21:1-21:37 (2011) - [j33]Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon:
Soft Constraints of Difference and Equality. J. Artif. Intell. Res. 41: 97-130 (2011) - [j32]Naonori Kakimura, Ken-ichi Kawarabayashi, Dániel Marx:
Packing cycles through prescribed vertices. J. Comb. Theory, Ser. B 101(5): 378-381 (2011) - [j31]Dániel Marx:
Tractable Structures for Constraint Satisfaction with Truth Tables. Theory Comput. Syst. 48(3): 444-464 (2011) - [j30]Noga Alon, Dániel Marx:
Sparse Balanced Partitions and the Complexity of Subgraph Problems. SIAM J. Discret. Math. 25(2): 631-644 (2011) - [j29]Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, Günter Rote:
Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension. ACM Trans. Algorithms 7(4): 43:1-43:27 (2011) - [j28]Dániel Marx:
Complexity of clique coloring and related problems. Theor. Comput. Sci. 412(29): 3487-3500 (2011) - 2010
- [j27]Dániel Marx:
Chordal Deletion is Fixed-Parameter Tractable. Algorithmica 57(4): 747-768 (2010) - [j26]Dániel Marx, Ildikó Schlotter:
Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties. Algorithmica 58(1): 170-187 (2010) - [j25]Andrei A. Bulatov, Dániel Marx:
Constraint satisfaction problems and global cardinality constraints. Commun. ACM 53(9): 99-106 (2010) - [j24]Andrei A. Bulatov, Dániel Marx:
The complexity of global cardinality constraints. Log. Methods Comput. Sci. 6(4) (2010) - [j23]Panos Giannopoulos, Rolf Klein, Christian Knauer, Martin Kutz, Dániel Marx:
Computing Geometric Minimum-Dilation Graphs is NP-Hard. Int. J. Comput. Geom. Appl. 20(2): 147-173 (2010) - [j22]Dániel Marx:
Approximating fractional hypertree width. ACM Trans. Algorithms 6(2): 29:1-29:17 (2010) - [j21]Dániel Marx:
Can You Beat Treewidth? Theory Comput. 6(1): 85-112 (2010) - 2009
- [j20]Dániel Marx, Marcus Schaefer:
The complexity of nonrepetitive coloring. Discret. Appl. Math. 157(1): 13-18 (2009) - [j19]Dániel Marx:
Complexity results for minimum sum edge coloring. Discret. Appl. Math. 157(5): 1034-1045 (2009) - [j18]Dániel Marx, Ildikó Schlotter:
Parameterized graph cleaning problems. Discret. Appl. Math. 157(15): 3258-3267 (2009) - [j17]Dániel Marx, Igor Razgon:
Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett. 109(20): 1161-1166 (2009) - [j16]Martin Grohe, Dániel Marx:
On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009) - [j15]Dániel Marx:
A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44): 4471-4479 (2009) - 2008
- [j14]Dániel Marx:
Parameterized Complexity and Approximation Algorithms. Comput. J. 51(1): 60-78 (2008) - [j13]Dániel Marx:
Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1): 31-36 (2008) - [j12]Dániel Marx:
Closest Substring Problems with Small Distances. SIAM J. Comput. 38(4): 1382-1410 (2008) - [j11]Dániel Marx:
Complexity of unique list colorability. Theor. Comput. Sci. 401(1-3): 62-76 (2008) - 2006
- [j10]Dániel Marx:
The complexity of chromatic strength and chromatic edge strength. Comput. Complex. 14(4): 308-340 (2006) - [j9]Dániel Marx:
Precoloring extension on unit interval graphs. Discret. Appl. Math. 154(6): 995-1002 (2006) - [j8]Dániel Marx:
Parameterized graph separation problems. Theor. Comput. Sci. 351(3): 394-406 (2006) - [j7]Dániel Marx:
Parameterized coloring problems on chordal graphs. Theor. Comput. Sci. 351(3): 407-424 (2006) - [j6]Dániel Marx:
Minimum sum multicoloring on the edges of trees. Theor. Comput. Sci. 361(2-3): 133-149 (2006) - 2005
- [j5]Dániel Marx:
Parameterized complexity of constraint satisfaction problems. Comput. Complex. 14(2): 153-183 (2005) - [j4]Dániel Marx:
NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory 49(4): 313-324 (2005) - [j3]Dániel Marx:
A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett. 33(4): 382-384 (2005) - 2004
- [j2]Dániel Marx:
Eulerian disjoint paths problem in grid graphs is NP-complete. Discret. Appl. Math. 143(1-3): 336-341 (2004) - [j1]Dániel Marx:
List edge multicoloring in graphs with few cycles. Inf. Process. Lett. 89(2): 85-90 (2004)
Conference and Workshop Papers
- 2024
- [c127]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations. SODA 2024: 314-345 - [c126]Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza:
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. SOSA 2024: 383-395 - 2023
- [c125]Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase:
Parameterized Approximation Schemes for Clustering with General Norm Objectives. FOCS 2023: 1377-1399 - [c124]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Approximate Monotone Local Search for Weighted Problems. IPEC 2023: 17:1-17:23 - [c123]Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek:
Computing Square Colorings on Bounded-Treewidth and Planar Graphs. SODA 2023: 2087-2110 - [c122]Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz:
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs. SODA 2023: 3664-3683 - 2022
- [c121]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser:
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. SoCG 2022: 20:1-20:17 - [c120]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. ESA 2022: 50:1-50:19 - [c119]Baris Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, Karol Wegrzycki:
Computing Generalized Convolutions Faster Than Brute Force. IPEC 2022: 12:1-12:22 - [c118]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Domination and Cut Problems on Chordal Graphs with Bounded Leafage. IPEC 2022: 14:1-14:24 - [c117]Dániel Marx, Govind S. Sankar, Philipp Schepper:
Anti-Factor Is FPT Parameterized by Treewidth and List Size (But Counting Is Hard). IPEC 2022: 22:1-22:23 - [c116]Jacob Focke, Dániel Marx, Pawel Rzazewski:
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. SODA 2022: 431-458 - [c115]Dániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale:
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs. SODA 2022: 2085-2127 - [c114]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Parameterized Complexity of Weighted Multicut in Trees. WG 2022: 257-270 - 2021
- [c113]Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram:
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC 2021: 3:1-3:18 - [c112]Dániel Marx, Govind S. Sankar, Philipp Schepper:
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth. ICALP 2021: 95:1-95:20 - [c111]Dániel Marx:
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction. PODS 2021: 19-29 - 2020
- [c110]Dániel Marx:
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth. Treewidth, Kernels, and Algorithms 2020: 129-144 - [c109]Marvin Künnemann, Dániel Marx:
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. CCC 2020: 27:1-27:28 - [c108]Dániel Marx:
Chordless Cycle Packing Is Fixed-Parameter Tractable. ESA 2020: 71:1-71:19 - [c107]Dániel Marx, R. B. Sandeep:
Incompressibility of H-Free Edge Modification Problems: Towards a Dichotomy. ESA 2020: 72:1-72:25 - [c106]Alexander Göke, Dániel Marx, Matthias Mnich:
Hitting Long Directed Cycles Is Fixed-Parameter Tractable. ICALP 2020: 59:1-59:18 - 2019
- [c105]Alexander Göke, Dániel Marx, Matthias Mnich:
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set. CIAC 2019: 249-261 - [c104]Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay:
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. SoCG 2019: 27:1-27:16 - [c103]Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh:
Parameterized Streaming Algorithms for Min-Ones d-SAT. FSTTCS 2019: 8:1-8:20 - [c102]Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
How Does Object Fatness Impact the Complexity of Packing in d Dimensions? ISAAC 2019: 36:1-36:18 - [c101]Benjamin Aram Berendsohn, László Kozma, Dániel Marx:
Finding and Counting Permutations via CSPs. IPEC 2019: 1:1-1:16 - 2018
- [c100]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. FOCS 2018: 474-484 - [c99]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-Budgeted Directed Cuts. IPEC 2018: 18:1-18:14 - [c98]Lin Chen, Dániel Marx:
Covering a tree with rooted subtrees - parameterized and approximation algorithms. SODA 2018: 2801-2820 - [c97]László Egri, Dániel Marx, Pawel Rzazewski:
Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. STACS 2018: 27:1-27:15 - [c96]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. STOC 2018: 574-586 - [c95]Andreas Emil Feldmann, Dániel Marx:
The Parameterized Hardness of the k-Center Problem in Transportation Networks. SWAT 2018: 19:1-19:13 - 2017
- [c94]Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski:
Fine-Grained Complexity of Coloring Unit Disks and Balls. SoCG 2017: 18:1-18:16 - [c93]Dániel Marx, Marcin Pilipczuk:
Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. ESA 2017: 59:1-59:15 - [c92]Dániel Marx:
Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk). ICDT 2017: 2:1-2:1 - [c91]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. IPEC 2017: 7:1-7:13 - [c90]Lin Chen, Dániel Marx, Deshi Ye, Guochuan Zhang:
Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. STACS 2017: 22:1-22:14 - [c89]Radu Curticapean, Holger Dell, Dániel Marx:
Homomorphisms are a good basis for counting small subgraphs. STOC 2017: 210-223 - 2016
- [c88]Dániel Marx, Ario Salmasi, Anastasios Sidiropoulos:
Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs. APPROX-RANDOM 2016: 16:1-16:54 - [c87]Dániel Marx, Tillmann Miltzow:
Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. SoCG 2016: 52:1-52:16 - [c86]Édouard Bonnet, László Egri, Dániel Marx:
Fixed-Parameter Approximability of Boolean MinCSPs. ESA 2016: 18:1-18:18 - [c85]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. FOCS 2016: 515-524 - [c84]Andreas Emil Feldmann, Dániel Marx:
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. ICALP 2016: 27:1-27:14 - [c83]Dániel Marx, Valia Mitsou:
Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. ICALP 2016: 28:1-28:15 - [c82]Gábor Bacsó, Dániel Marx, Zsolt Tuza:
H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. IPEC 2016: 3:1-3:12 - [c81]Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich:
Routing with Congestion in Acyclic Digraphs. MFCS 2016: 7:1-7:11 - [c80]Radu Curticapean, Dániel Marx:
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. SODA 2016: 1650-1669 - [c79]MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. STOC 2016: 570-583 - [c78]Dániel Marx:
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems (Invited Talk). SWAT 2016: 32:1-32:1 - [c77]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property. WG 2016: 233-244 - 2015
- [c76]Dániel Marx, Michal Pilipczuk:
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. ESA 2015: 865-877 - [c75]Bart M. P. Jansen, Dániel Marx:
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. SODA 2015: 616-629 - [c74]Dániel Marx, Paul Wollan:
An exact characterization of tractable demand patterns for maximum disjoint path problems. SODA 2015: 642-661 - 2014
- [c73]Dániel Marx, Anastasios Sidiropoulos:
The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. SoCG 2014: 67 - [c72]Radu Curticapean, Dániel Marx:
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. FOCS 2014: 130-139 - [c71]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth. MFCS (2) 2014: 189-200 - [c70]Sylvain Guillemot, Dániel Marx:
Finding small patterns in permutations in linear time. SODA 2014: 82-101 - [c69]Yixin Cao, Dániel Marx:
Interval Deletion is Fixed-Parameter Tractable. SODA 2014: 122-141 - [c68]Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). SODA 2014: 1782-1801 - [c67]Philip N. Klein, Dániel Marx:
A subexponential parameterized algorithm for Subset TSP on planar graphs. SODA 2014: 1812-1830 - [c66]Yixin Cao, Dániel Marx:
Chordal Editing is Fixed-Parameter Tractable. STACS 2014: 214-225 - [c65]Dániel Marx, Michal Pilipczuk:
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). STACS 2014: 542-553 - 2013
- [c64]Dániel Marx:
The Square Root Phenomenon in Planar Graphs. FAW-AAIM 2013: 1 - [c63]Rajesh Hemant Chitnis, László Egri, Dániel Marx:
List H-Coloring a Graph by Removing Few Vertices. ESA 2013: 313-324 - [c62]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. FOCS 2013: 197-206 - [c61]Dániel Marx:
The Square Root Phenomenon in Planar Graphs. ICALP (2) 2013: 28 - [c60]Hubie Chen, Dániel Marx:
Block-Sorted Quantified Conjunctive Queries. ICALP (2) 2013: 125-136 - [c59]Dániel Marx, László A. Végh:
Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation. ICALP (1) 2013: 721-732 - [c58]Sylvain Guillemot, Dániel Marx:
A Faster FPT Algorithm for Bipartite Contraction. IPEC 2013: 177-188 - [c57]Dániel Marx:
Algorithmic Graph Structure Theory (Tutorial). STACS 2013: 7-7 - 2012
- [c56]Fedor V. Fomin, Dániel Marx:
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows. The Multivariate Algorithmic Revolution and Beyond 2012: 457-468 - [c55]Dániel Marx:
What's Next? Future Directions in Parameterized Complexity. The Multivariate Algorithmic Revolution and Beyond 2012: 469-496 - [c54]Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström:
On Problems as Hard as CNF-SAT. CCC 2012: 74-84 - [c53]Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Dániel Marx:
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2012: 230-241 - [c52]Philip N. Klein, Dániel Marx:
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. ICALP (1) 2012: 569-580 - [c51]Dániel Marx:
A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. ICALP (1) 2012: 677-688 - [c50]Dániel Marx:
Randomized Techniques for Parameterized Algorithms. IPEC 2012: 2 - [c49]Holger Dell, Dániel Marx:
Kernelization of packing problems. SODA 2012: 68-81 - [c48]Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SODA 2012: 1713-1725 - [c47]Martin Grohe, Dániel Marx:
Structure theorem and isomorphism test for graphs with excluded topological subgraphs. STOC 2012: 173-192 - [c46]Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra, Yngve Villanger:
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties. WG 2012: 332-343 - 2011
- [c45]David A. Cohen, Martin C. Cooper, Martin James Green, Dániel Marx:
On Guaranteeing Polynomially Bounded Search Tree Size. CP 2011: 160-171 - [c44]Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. ICALP (1) 2011: 424-436 - [c43]Daniel Lokshtanov, Dániel Marx:
Clustering with Local Restrictions. ICALP (1) 2011: 785-797 - [c42]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. SODA 2011: 760-776 - [c41]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. SODA 2011: 777-789 - [c40]MohammadHossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, Dániel Marx:
Prize-collecting Steiner Problems on Planar Graphs. SODA 2011: 1028-1049 - [c39]Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC 2011: 469-478 - [c38]Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan:
Finding topological subgraphs is fixed-parameter tractable. STOC 2011: 479-488 - [c37]Dániel Marx:
Important Separators and Parameterized Algorithms. WG 2011: 5-10 - [c36]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter:
Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142 - 2010
- [c35]Dániel Marx:
Completely Inapproximable Monotone and Antimonotone Parameterized Problems. CCC 2010: 181-187 - [c34]Stefan Kratsch, Dániel Marx, Magnus Wahlström:
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. MFCS 2010: 489-500 - [c33]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Treewidth Reduction for Constrained Separation and Bipartization Problems. STACS 2010: 561-572 - [c32]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx:
Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. STOC 2010: 211-220 - [c31]Dániel Marx:
Tractable hypergraph properties for constraint satisfaction and conjunctive queries. STOC 2010: 735-744 - [c30]Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter:
Bin Packing with Fixed Number of Bins Revisited. SWAT 2010: 260-272 - [c29]Dániel Marx, Ildikó Schlotter:
Parameterized Complexity of the Arc-Preserving Subsequence Problem. WG 2010: 244-255 - 2009
- [c28]Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon:
Constraints of Difference and Equality: A Complete Taxonomic Characterisation. CP 2009: 424-438 - [c27]Dániel Marx, Igor Razgon:
Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. ESA 2009: 647-658 - [c26]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. ESA 2009: 718-729 - [c25]Dániel Marx, Ildikó Schlotter:
Stable Assignment with Couples: Parameterized Complexity and Local Search. IWPEC 2009: 300-311 - [c24]Andrei A. Bulatov, Dániel Marx:
The Complexity of Global Cardinality Constraints. LICS 2009: 419-428 - [c23]Dániel Marx:
Approximating fractional hypertree width. SODA 2009: 902-911 - [c22]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. STACS 2009: 231-242 - [c21]Dániel Marx:
Tractable Structures for Constraint Satisfaction with Truth Tables. STACS 2009: 649-660 - 2008
- [c20]Albert Atserias, Martin Grohe, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748 - [c19]Andrei A. Krokhin, Dániel Marx:
On the Hardness of Losing Weight. ICALP (1) 2008: 662-673 - [c18]Dániel Marx, Ildikó Schlotter:
Parameterized Graph Cleaning Problems. WG 2008: 287-299 - 2007
- [c17]Dániel Marx:
Can you beat treewidth? FOCS 2007: 169-179 - [c16]Dániel Marx:
On the Optimality of Planar and Geometric Approximation Schemes. FOCS 2007: 338-348 - [c15]Dániel Marx, Ildikó Schlotter:
Obtaining a Planar Graph by Vertex Deletion. WG 2007: 292-303 - 2006
- [c14]Dániel Marx:
A Parameterized View on Matroid Optimization Problems. ACiD 2006: 158 - [c13]Dániel Marx:
A Parameterized View on Matroid Optimization Problems. ICALP (1) 2006: 655-666 - [c12]Dániel Marx:
Parameterized Complexity of Independence and Domination on Geometric Graphs. IWPEC 2006: 154-165 - [c11]Martin Grohe, Dániel Marx:
Constraint solving via fractional edge covers. SODA 2006: 289-298 - [c10]Dániel Marx:
Chordal Deletion Is Fixed-Parameter Tractable. WG 2006: 37-48 - 2005
- [c9]Dániel Marx:
Efficient Approximation Schemes for Geometric Problems?. ESA 2005: 448-459 - [c8]Dániel Marx:
The Closest Substring problem with small distances. FOCS 2005: 63-72 - 2004
- [c7]Dániel Marx:
Parameterized Complexity of Constraint Satisfaction Problems. CCC 2004: 139-149 - [c6]Dániel Marx:
Parameterized Graph Separation Problems. IWPEC 2004: 71-82 - [c5]Dániel Marx:
Parameterized Coloring Problems on Chordal Graphs. IWPEC 2004: 83-95 - [c4]Dániel Marx:
Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees. WAOA 2004: 9-22 - 2003
- [c3]Dániel Marx:
Minimum Sum Multicoloring on the Edges of Trees: (Extended Abstract). WAOA 2003: 214-226 - 2002
- [c2]Dániel Marx:
The Complexity of Tree Multicolorings. MFCS 2002: 532-542 - 2000
- [c1]Tibor Cinkler, Dániel Marx, Claus Popp Larsen, Dániel Fogaras:
Heuristic Algorithms for Joint Configuration of the Optical and Electrical Layer in Multi-Hop Wavelength Routing Networks. INFOCOM 2000: 1000-1009
Editorship
- 2021
- [e6]Dániel Marx:
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021. SIAM 2021, ISBN 978-1-61197-646-5 [contents] - 2018
- [e5]Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella:
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. LIPIcs 107, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-076-7 [contents] - 2012
- [e4]Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, Dániel Marx:
The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science 7370, Springer 2012, ISBN 978-3-642-30890-1 [contents] - [e3]Dániel Marx, Peter Rossmanith:
Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. Lecture Notes in Computer Science 7112, Springer 2012, ISBN 978-3-642-28049-8 [contents] - 2009
- [e2]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Parameterized complexity and approximation algorithms, 13.12. - 17.12.2009. Dagstuhl Seminar Proceedings 09511, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - 2007
- [e1]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007. Dagstuhl Seminar Proceedings 07281, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2007 [contents]
Informal and Other Publications
- 2024
- [i106]Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski:
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. CoRR abs/2402.07331 (2024) - [i105]Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Roohani Sharma, Karol Wegrzycki:
Hitting Meets Packing: How Hard Can it Be? CoRR abs/2402.14927 (2024) - 2023
- [i104]Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase:
Parameterized Approximation Schemes for Clustering with General Norm Objectives. CoRR abs/2304.03146 (2023) - [i103]Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, Joachim Spoerhase:
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces. CoRR abs/2305.07316 (2023) - [i102]Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz:
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results. CoRR abs/2306.03640 (2023) - [i101]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations. CoRR abs/2306.15331 (2023) - [i100]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Approximate Monotone Local Search for Weighted Problems. CoRR abs/2308.15306 (2023) - [i99]Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza:
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof. CoRR abs/2311.05913 (2023) - [i98]Simon Döring, Dániel Marx, Philip Wellnitz:
Counting Small Induced Subgraphs with Edge-monotone Properties. CoRR abs/2311.08988 (2023) - [i97]Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx:
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern. CoRR abs/2312.11086 (2023) - 2022
- [i96]Dániel Marx:
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction. CoRR abs/2203.07717 (2022) - [i95]Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann, Dániel Marx, André Nusser:
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. CoRR abs/2203.07898 (2022) - [i94]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Parameterized Complexity of Weighted Multicut in Trees. CoRR abs/2205.10105 (2022) - [i93]Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen, Roohani Sharma:
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search. CoRR abs/2206.13481 (2022) - [i92]Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, Prafullkumar Tale:
Domination and Cut Problems on Chordal Graphs with Bounded Leafage. CoRR abs/2208.02850 (2022) - [i91]Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, Roohani Sharma:
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification. CoRR abs/2208.06015 (2022) - [i90]Baris Can Esmer, Ariel Kulik, Dániel Marx, Philipp Schepper, Karol Wegrzycki:
Computing Generalized Convolutions Faster Than Brute Force. CoRR abs/2209.01623 (2022) - [i89]Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski:
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs. CoRR abs/2210.10677 (2022) - [i88]Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz:
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results. CoRR abs/2211.04278 (2022) - [i87]Akanksha Agrawal, Dániel Marx, Daniel Neuen, Jasper Slusallek:
Computing Square Colorings on Bounded-Treewidth and Planar Graphs. CoRR abs/2211.04458 (2022) - [i86]Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports 12(5): 112-130 (2022) - 2021
- [i85]Dániel Marx, Govind S. Sankar, Philipp Schepper:
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth. CoRR abs/2105.08980 (2021) - [i84]Jacob Focke, Dániel Marx, Pawel Rzazewski:
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. CoRR abs/2107.06889 (2021) - [i83]Dániel Marx, Govind S. Sankar, Philipp Schepper:
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard). CoRR abs/2110.09369 (2021) - [i82]Dániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale:
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs. CoRR abs/2110.15098 (2021) - 2020
- [i81]Alexander Göke, Dániel Marx, Matthias Mnich:
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set. CoRR abs/2003.02483 (2020) - [i80]Alexander Göke, Dániel Marx, Matthias Mnich:
Hitting Long Directed Cycles is Fixed-Parameter Tractable. CoRR abs/2003.05267 (2020) - [i79]Dániel Marx, R. B. Sandeep:
Incompressibility of H-free edge modification problems: Towards a dichotomy. CoRR abs/2004.11761 (2020) - [i78]Marvin Künnemann, Dániel Marx:
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction. CoRR abs/2005.11541 (2020) - [i77]Dániel Marx:
Four short stories on surprising algorithmic uses of treewidth. CoRR abs/2008.07968 (2020) - [i76]Vincent Cohen-Addad, Philip N. Klein, Dániel Marx:
On the computational tractability of a geographic clustering problem arising in redistricting. CoRR abs/2009.00188 (2020) - 2019
- [i75]Lin Chen, Dániel Marx:
Covering a tree with rooted subtrees. CoRR abs/1902.08218 (2019) - [i74]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Slightly Superexponential Parameterized Problems. CoRR abs/1902.08723 (2019) - [i73]Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, Arnaud de Mesmay:
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. CoRR abs/1903.08603 (2019) - [i72]Benjamin Aram Berendsohn, László Kozma, Dániel Marx:
Finding and counting permutations via CSPs. CoRR abs/1908.04673 (2019) - [i71]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR abs/1909.01986 (2019) - [i70]Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
How does object fatness impact the complexity of packing in d dimensions? CoRR abs/1909.12044 (2019) - [i69]Rajesh Chitnis, Andreas Emil Feldmann, MohammadTaghi Hajiaghayi, Dániel Marx:
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). CoRR abs/1911.13161 (2019) - [i68]Fedor V. Fomin, Dániel Marx, Saket Saurabh, Meirav Zehavi:
New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). Dagstuhl Reports 9(1): 67-87 (2019) - [i67]Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i66]Andreas Emil Feldmann, Dániel Marx:
The Parameterized Hardness of the k-Center Problem in Transportation Networks. CoRR abs/1802.08563 (2018) - [i65]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden:
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs. CoRR abs/1803.10633 (2018) - [i64]Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen:
Subexponential-time Algorithms for Maximum Independent Set in Pt-free and Broom-free Graphs. CoRR abs/1804.04077 (2018) - [i63]Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted directed cuts. CoRR abs/1810.06848 (2018) - [i62]Holger Dell, Dániel Marx:
Kernelization of Packing Problems. CoRR abs/1812.03155 (2018) - 2017
- [i61]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms. CoRR abs/1704.06757 (2017) - [i60]Radu Curticapean, Holger Dell, Dániel Marx:
Homomorphisms Are a Good Basis for Counting Small Subgraphs. CoRR abs/1705.01595 (2017) - [i59]Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs. CoRR abs/1707.02190 (2017) - [i58]Andreas Emil Feldmann, Dániel Marx:
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. CoRR abs/1707.06808 (2017) - [i57]Albert Atserias, Martin Grohe, Dániel Marx:
Size bounds and query plans for relational joins. CoRR abs/1711.03860 (2017) - [i56]Daniel Lokshtanov, Dániel Marx:
Clustering with Local Restrictions. CoRR abs/1711.03885 (2017) - [i55]Dániel Marx:
Completely inapproximable monotone and antimonotone parameterized problems. CoRR abs/1711.03886 (2017) - [i54]Andrei A. Krokhin, Dániel Marx:
On the hardness of losing weight. CoRR abs/1711.03894 (2017) - [i53]Martin Grohe, Dániel Marx:
Constraint Solving via Fractional Edge Covers. CoRR abs/1711.04506 (2017) - 2016
- [i52]Dániel Marx, Ario Salmasi, Anastasios Sidiropoulos:
Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs. CoRR abs/1601.01372 (2016) - [i51]Édouard Bonnet, László Egri, Dániel Marx:
Fixed-parameter Approximability of Boolean MinCSPs. CoRR abs/1601.04935 (2016) - [i50]Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx:
Parameterized vertex deletion problems for hereditary graph classes with a block property. CoRR abs/1603.05945 (2016) - [i49]Dániel Marx, Tillmann Miltzow:
Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. CoRR abs/1603.07340 (2016) - [i48]Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. CoRR abs/1604.05999 (2016) - [i47]Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich:
Routing with Congestion in Acyclic Digraphs. CoRR abs/1605.01866 (2016) - [i46]Dániel Marx, Marcin Pilipczuk:
Subexponential parameterized algorithms for graphs of polynomial growth. CoRR abs/1610.07778 (2016) - [i45]Dániel Marx, Anastasios Sidiropoulos:
The limited blessing of low dimensionality: when $1-1/d$ is the best possible exponent for $d$-dimensional geometric problems. CoRR abs/1612.01171 (2016) - [i44]Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu:
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports 6(5): 94-116 (2016) - 2015
- [i43]Dániel Marx, Michal Pilipczuk:
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. CoRR abs/1504.05476 (2015) - [i42]Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, Nicolas Trotignon:
Colouring graphs with constraints on connectivity. CoRR abs/1505.01616 (2015) - [i41]Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports 5(7): 22-41 (2015) - 2014
- [i40]Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon:
Soft Constraints of Difference and Equality. CoRR abs/1401.3879 (2014) - [i39]Yixin Cao, Dániel Marx:
Chordal Editing is Fixed-Parameter Tractable. CoRR abs/1405.7859 (2014) - [i38]Radu Curticapean, Dániel Marx:
Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014) - [i37]Bart M. P. Jansen, Dániel Marx:
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. CoRR abs/1410.0855 (2014) - [i36]Dániel Marx, Paul Wollan:
An exact characterization of tractable demand patterns for maximum disjoint path problems. CoRR abs/1411.0871 (2014) - [i35]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
Hitting forbidden subgraphs in graphs of bounded treewidth. CoRR abs/1411.4184 (2014) - [i34]Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, Peter Rossmanith:
Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). Dagstuhl Reports 4(11): 1-21 (2014) - 2013
- [i33]Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk:
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable. CoRR abs/1304.4207 (2013) - [i32]Dániel Marx, László A. Végh:
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation. CoRR abs/1304.6593 (2013) - [i31]Sylvain Guillemot, Dániel Marx:
A faster FPT algorithm for Bipartite Contraction. CoRR abs/1305.2743 (2013) - [i30]Dániel Marx, Michal Pilipczuk:
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). CoRR abs/1307.2187 (2013) - [i29]Sylvain Guillemot, Dániel Marx:
Finding small patterns in permutations in linear time. CoRR abs/1307.3073 (2013) - [i28]Rajesh Hemant Chitnis, László Egri, Dániel Marx:
List H-Coloring a Graph by Removing Few Vertices. CoRR abs/1308.1068 (2013) - [i27]Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu:
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports 3(10): 36-57 (2013) - 2012
- [i26]Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx:
Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. CoRR abs/1205.1271 (2012) - [i25]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
Minimizing Movement: Fixed-Parameter Tractability. CoRR abs/1205.6960 (2012) - [i24]Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlen:
Exponential Time Complexity of the Permanent and the Tutte Polynomial. CoRR abs/1206.1775 (2012) - [i23]Andrei A. Bulatov, Dániel Marx:
Constraint satisfaction parameterized by solution size. CoRR abs/1206.4854 (2012) - [i22]Yixin Cao, Dániel Marx:
Interval Deletion is Fixed-Parameter Tractable. CoRR abs/1211.5933 (2012) - [i21]Michael R. Fellows, Jiong Guo, Dániel Marx, Saket Saurabh:
Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). Dagstuhl Reports 2(6): 26-50 (2012) - [i20]Johan Håstad, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports 2(11): 1-19 (2012) - 2011
- [i19]Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. CoRR abs/1110.0259 (2011) - [i18]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Finding small separators in linear time via treewidth reduction. CoRR abs/1110.4765 (2011) - [i17]Martin Grohe, Dániel Marx:
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. CoRR abs/1111.1109 (2011) - [i16]Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström:
On Problems as Hard as CNFSAT. CoRR abs/1112.2275 (2011) - 2010
- [i15]Dániel Marx, Ildikó Schlotter:
Cleaning Interval Graphs. CoRR abs/1003.1260 (2010) - [i14]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx:
Prize-collecting Network Design on Planar Graphs. CoRR abs/1006.4339 (2010) - [i13]Daniel Lokshtanov, Dániel Marx, Saket Saurabh:
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. CoRR abs/1007.5450 (2010) - [i12]Dániel Marx, Igor Razgon:
Fixed-parameter tractability of multicut parameterized by the size of the cutset. CoRR abs/1010.3633 (2010) - [i11]Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan:
Finding topological subgraphs is fixed-parameter tractable. CoRR abs/1011.1827 (2010) - 2009
- [i10]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Abstracts Collection - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i9]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Executive Summary - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i8]Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx:
09511 Open Problems - Parameterized complexity and approximation algorithms. Parameterized complexity and approximation algorithms 2009 - [i7]Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms. CoRR abs/0902.1256 (2009) - [i6]Dániel Marx, Barry O'Sullivan, Igor Razgon:
Treewidth reduction for constrained separation and bipartization problems. CoRR abs/0902.3780 (2009) - [i5]Dániel Marx:
Tractable hypergraph properties for constraint satisfaction and conjunctive queries. CoRR abs/0911.0801 (2009) - [i4]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx:
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. CoRR abs/0911.5143 (2009) - 2008
- [i3]Dániel Marx, Ildikó Schlotter:
Obtaining a Planar Graph by Vertex Deletion. CoRR abs/0812.4919 (2008) - 2007
- [i2]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
07281 Abstracts Collection -- Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007 - [i1]Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, Ulrike Stege:
07281 Open Problems -- Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs 2007
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-05-08 23:29 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
