Dániel Marx

Logic in Computer Science, Humbold-Universität Berlin, Germany

	2013
j44		Dániel Marx, Ildikó Schlotter: Cleaning Interval Graphs. Algorithmica 65(2): 275-316 (2013)
j43		Daniel Lokshtanov, Dániel Marx: Clustering with local restrictions. Inf. Comput. 222: 278-292 (2013)
j42		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)
j41		Dániel Marx: Completely inapproximable monotone and antimonotone parameterized problems. J. Comput. Syst. Sci. 79(1): 144-151 (2013)
c60		Dániel Marx: The Square Root Phenomenon in Planar Graphs. FAW-AAIM 2013: 1
c59		Dániel Marx: Algorithmic Graph Structure Theory (Tutorial). STACS 2013: 7-7
i23		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)
i22		Dániel Marx, László A. Végh: Fixed-parameter algorithms for minimum cost edge-connectivity augmentation. CoRR abs/1304.6593 (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. (JAIR) 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 Transactions on Algorithms 8(2): 19 (2012)
c58		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
c57		Dániel Marx: What's Next? Future Directions in Parameterized Complexity. The Multivariate Algorithmic Revolution and Beyond 2012: 469-496
c56		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. IEEE Conference on Computational Complexity 2012: 74-84
c55		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
c54		Philip N. Klein, Dániel Marx: Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. ICALP (1) 2012: 569-580
c53		Dániel Marx: A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. ICALP (1) 2012: 677-688
c52		Dániel Marx: Randomized Techniques for Parameterized Algorithms. IPEC 2012: 2
c51		Holger Dell, Dániel Marx: Kernelization of packing problems. SODA 2012: 68-81
c50		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
c49		Martin Grohe, Dániel Marx: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. STOC 2012: 173-192
c48		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
e3		Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, Dániel Marx (Eds.): 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
e2		Dániel Marx, Peter Rossmanith (Eds.): 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
i21		Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Dániel Marx: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. CoRR abs/1205.1271 (2012)
i20		Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx: Minimizing Movement: Fixed-Parameter Tractability. CoRR abs/1205.6960 (2012)
i19		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)
i18		Andrei A. Bulatov, Dániel Marx: Constraint satisfaction parameterized by solution size. CoRR abs/1206.4854 (2012)
i17		Yixin Cao, Dániel Marx: Interval Deletion is Fixed-Parameter Tractable. CoRR abs/1211.5933 (2012)
i16		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)
i15		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
j36		Dániel Marx, Ildikó Schlotter: Stable assignment with couples: Parameterized complexity and local search. Discrete Optimization 8(1): 25-40 (2011)
j35		Daniel Lokshtanov, Dániel Marx, Saket Saurabh: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the 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 (2011)
j33		Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon: Soft Constraints of Difference and Equality. J. Artif. Intell. Res. (JAIR) 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. Discrete 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 Transactions on Algorithms 7(4): 43 (2011)
j28		Dániel Marx: Complexity of clique coloring and related problems. Theor. Comput. Sci. 412(29): 3487-3500 (2011)
c47		David A. Cohen, Martin C. Cooper, Martin J. Green, Dániel Marx: On Guaranteeing Polynomially Bounded Search Tree Size. CP 2011: 160-171
c46		Andrei A. Bulatov, Dániel Marx: Constraint Satisfaction Parameterized by Solution Size. ICALP (1) 2011: 424-436
c45		Daniel Lokshtanov, Dániel Marx: Clustering with Local Restrictions. ICALP (1) 2011: 785-797
c44		Daniel Lokshtanov, Dániel Marx, Saket Saurabh: Slightly Superexponential Parameterized Problems. SODA 2011: 760-776
c43		Daniel Lokshtanov, Dániel Marx, Saket Saurabh: Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal. SODA 2011: 777-789
c42		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
c41		Dániel Marx, Igor Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC 2011: 469-478
c40		Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable. STOC 2011: 479-488
c39		Dániel Marx: Important Separators and Parameterized Algorithms. WG 2011: 5-10
c38		Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Ildikó Schlotter: Parameterized Complexity of Eulerian Deletion Problems. WG 2011: 131-142
i14		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)
i13		Dániel Marx, Barry O'Sullivan, Igor Razgon: Finding small separators in linear time via treewidth reduction. CoRR abs/1110.4765 (2011)
i12		Martin Grohe, Dániel Marx: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs. CoRR abs/1111.1109 (2011)
i11		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
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. Logical Methods in Computer Science 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. Geometry Appl. 20(2): 147-173 (2010)
j22		Dániel Marx: Approximating fractional hypertree width. ACM Transactions on Algorithms 6(2) (2010)
j21		Dániel Marx: Can You Beat Treewidth? Theory of Computing 6(1): 85-112 (2010)
c37		Dániel Marx: Completely Inapproximable Monotone and Antimonotone Parameterized Problems. IEEE Conference on Computational Complexity 2010: 181-187
c36		Stefan Kratsch, Dániel Marx, Magnus Wahlström: Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. MFCS 2010: 489-500
c35		Dániel Marx, Barry O'Sullivan, Igor Razgon: Treewidth Reduction for Constrained Separation and Bipartization Problems. STACS 2010: 561-572
c34		MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. STOC 2010: 211-220
c33		Dániel Marx: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. STOC 2010: 735-744
c32		Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter: Bin Packing with Fixed Number of Bins Revisited. SWAT 2010: 260-272
c31		Dániel Marx, Ildikó Schlotter: Parameterized Complexity of the Arc-Preserving Subsequence Problem. WG 2010: 244-255
i10		Dániel Marx, Ildikó Schlotter: Cleaning Interval Graphs. CoRR abs/1003.1260 (2010)
i9		MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx: Prize-collecting Network Design on Planar Graphs. CoRR abs/1006.4339 (2010)
i8		Daniel Lokshtanov, Dániel Marx, Saket Saurabh: Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. CoRR abs/1007.5450 (2010)
i7		Dániel Marx, Igor Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset. CoRR abs/1010.3633 (2010)
i6		Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan: Finding topological subgraphs is fixed-parameter tractable. CoRR abs/1011.1827 (2010)
	2009
j20		Dániel Marx, Marcus Schaefer: The complexity of nonrepetitive coloring. Discrete Applied Mathematics 157(1): 13-18 (2009)
j19		Dániel Marx: Complexity results for minimum sum edge coloring. Discrete Applied Mathematics 157(5): 1034-1045 (2009)
j18		Dániel Marx, Ildikó Schlotter: Parameterized graph cleaning problems. Discrete Applied Mathematics 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)
c30		Emmanuel Hebrard, Dániel Marx, Barry O'Sullivan, Igor Razgon: Constraints of Difference and Equality: A Complete Taxonomic Characterisation. CP 2009: 424-438
c29		Dániel Marx, Igor Razgon: Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem. ESA 2009: 647-658
c28		Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx: Minimizing Movement: Fixed-Parameter Tractability. ESA 2009: 718-729
c27		Dániel Marx, Ildikó Schlotter: Stable Assignment with Couples: Parameterized Complexity and Local Search. IWPEC 2009: 300-311
c26		Andrei A. Bulatov, Dániel Marx: The Complexity of Global Cardinality Constraints. LICS 2009: 419-428
c25		Dániel Marx: Approximating fractional hypertree width. SODA 2009: 902-911
c24		Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms. STACS 2009: 231-242
c23		Dániel Marx: Tractable Structures for Constraint Satisfaction with Truth Tables. STACS 2009: 649-660
i5		Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx: Enumerating Homomorphisms. CoRR abs/0902.1256 (2009)
i4		Dániel Marx, Barry O'Sullivan, Igor Razgon: Treewidth reduction for constrained separation and bipartization problems. CoRR abs/0902.3780 (2009)
i3		Dániel Marx: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. CoRR abs/0911.0801 (2009)
i2		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
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)
c22		Albert Atserias, Martin Grohe, Dániel Marx: Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748
c21		Andrei A. Krokhin, Dániel Marx: On the Hardness of Losing Weight. ICALP (1) 2008: 662-673
c20		Dániel Marx, Ildikó Schlotter: Parameterized Graph Cleaning Problems. WG 2008: 287-299
i1		Dániel Marx, Ildikó Schlotter: Obtaining a Planar Graph by Vertex Deletion. CoRR abs/0812.4919 (2008)
	2007
c19		Erik D. Demaine, Gregory 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
c18		Erik D. Demaine, Gregory 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
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
e1		Erik D. Demaine, Gregory Gutin, Dániel Marx, Ulrike Stege (Eds.): 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
	2006
j10		Dániel Marx: The complexity of chromatic strength and chromatic edge strength. Computational Complexity 14(4): 308-340 (2006)
j9		Dániel Marx: Precoloring extension on unit interval graphs. Discrete Applied Mathematics 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)
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
j5		Dániel Marx: Parameterized complexity of constraint satisfaction problems. Computational Complexity 14(2): 153-183 (2005)
j4		Dániel Marx: NP-completeness of list coloring and precoloring extension on the edges of planar graphs. Journal of 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)
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
j2		Dániel Marx: Eulerian disjoint paths problem in grid graphs is NP-complete. Discrete Applied Mathematics 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)
c7		Dániel Marx: Parameterized Complexity of Constraint Satisfaction Problems. IEEE Conference on Computational Complexity 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

Coauthor Index

Colors in the list of coauthors

Last update Sat May 25 10:17:43 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page