Ugrás a tartalomhoz

EU Kiválósági KözpontISO 9001

ERCIMW3C MemberFraunhofer Projektközpont

Marx Dániel, Ph.D., tudományos főmunkatárs, kutató
Marx Dániel
Cím: 1111 Budapest, Lágymányosi u. 11.
Szoba: L 410
Telefon: +36 1 279 6167
E-mail: dmarxEZT_TOROLJE_KI@EZT_TOROLJE_KIsztaki.hu
Honlap: http://www.cs.bme.hu/~dmarx/
Részleg: Informatikai Kutatólaboratórium

Publikációk

[Időrendben] [Kategóriákba sorolva ]

2019.

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms
Szerzők: Bonnet, É; Brettell, N; Kwon, O-J; Marx, Dániel
Megjelenés: 2019.
Megjelent: ALGORITHMICA (Kötetszám: 81, Füzetszám: 10, Oldalszám: 3890-3935)
Almost tight lower bounds for hard cutting problems in embedded graphs
Szerzők: Cohen-Addad, V; de, Verdière É C; Marx, Dániel; de, Mesmay A
Megjelenés: 2019.
Megjelent: (Füzetszám: 129, Oldalszám: 27:1-27:16)

2018.

Slightly Superexponential Parameterized Problems
Szerzők: Lokshtanov, D; Marx, Dániel; Saurabh, S
Megjelenés: 2018.
Megjelent: SIAM JOURNAL ON COMPUTING (Kötetszám: 47, Füzetszám: 3, Oldalszám: 675-702)
Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs
Szerzők: Bacsó, Gábor; Lokshtanov, D; Marx, Dániel; Pilipczuk, M; Tuza, Zsolt
Megjelenés: 2018.
Megjelent: ALGORITHMICA (Kötetszám: xx, Füzetszám: x, Oldalszám: 1-18)
A framework for ETH-Tight algorithms and lower bounds in geometric intersection graphs
Szerzők: De, Berg M; Bodlaender, HL; Kisfaludi-Bak, S; Marx, Dániel; Van, Der Zanden TC
Megjelenés: 2018.
Megjelent: (Oldalszám: 51-64)
The parameterized hardness of the k-center problem in transportation networks
Szerzők: Feldmann, AE; Marx, Dániel
Szerkesztő: Eppstein, D
Megjelenés: 2018.
Megjelent: (Füzetszám: 101, Oldalszám: 191-1913)
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs
Szerzők: Marx, Dániel; Pilipczuk, M; Pilipczuk, M
Megjelenés: 2018.
Megjelent: (Oldalszám: 474-484)
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
Szerzők: Lokshtanov, D; Marx, Dániel; Saurabh, S
Megjelenés: 2018.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 14, Füzetszám: 2)
Covering a tree with rooted subtrees -parameterized and approximation algorithms
Szerzők: Chen, L; Marx, Dániel
Megjelenés: 2018.
Megjelent: (Oldalszám: 2801-2820)
Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: A complete complexity characterization
Szerzők: Egri, L; Marx, Dániel; Rzazewski, P
Megjelenés: 2018.
Megjelent: (Füzetszám: 96, Oldalszám: 27:1-27:15)
Fine-grained complexity of coloring unit disks and balls
Szerzők: Biró, Cs; Bonnet, É; Marx, Dániel; Miltzow, T; Rzazewski, P
Megjelenés: 2018.
Megjelent: JOURNAL OF COMPUTATIONAL GEOMETRY (Kötetszám: 9, Füzetszám: 2, Oldalszám: 47-87)
Generalized Feedback Vertex set problems on bounded-treewidth graphs: Chordality is the key to single-exponential parameterized algorithms
Szerzők: Bonnet, E; Brettell, N; Kwon, OJ; Marx, Dániel
Megjelenés: 2018.
Megjelent: (Füzetszám: 89, Oldalszám: 7:1-7:13)
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Szerzők: Chatzigiannakis, I; Kaklamanis, C; Marx, Dániel; Sannella, D
Szerkesztő: Chatzigiannakis, I; Kaklamanis, C; Marx, Dániel; Sannella, D
Megjelenés: 2018.
Megjelent: (Füzetszám: 107)

2017.

Parameterized and approximation results for scheduling with a low rank processing time matrix
Szerzők: Chen, L; Marx, Dániel; Ye, D; Zhang, G
Szerkesztő: Vollmer, H; Vallée, B
Megjelenés: 2017.
Megjelent: (Füzetszám: 66, Oldalszám: 22:1-22:14)
Rooted grid minors
Szerzők: Marx, Dániel; Seymour, P; Wollan, P
Megjelenés: 2017.
Megjelent: JOURNAL OF COMBINATORIAL THEORY SERIES B (Kötetszám: 122, Oldalszám: 428-437)
Subexponential parameterized algorithms for graphs of polynomial growth
Szerzők: Marx, Dániel; Pilipczuk, M
Szerkesztő: Kirk, Pruhs; Christian, Sohler
Megjelenés: 2017.
Megjelent: (Füzetszám: 87, Oldalszám: 59:1-59:15)
List H-Coloring a Graph by Removing Few Vertices
Szerzők: Chitnis, R; Egri, L; Marx, Dániel
Megjelenés: 2017.
Megjelent: ALGORITHMICA (Kötetszám: 78, Füzetszám: 1, Oldalszám: 110-146)
Homomorphisms are a good basis for counting small subgraphs
Szerzők: Curticapean, Radu; Dell, H; Marx, Dániel
Szerkesztő: McKenzie, P; King, V; Hatami, H
Megjelenés: 2017.
Megjelent: (Oldalszám: 210-223)
Fine-grained complexity of coloring unit disks and balls
Szerzők: Biró, C; Bonnet, É; Marx, Dániel; Miltzow, Tillmann; Rzazewski, Pavel Michael
Szerkesztő: Katz, MJ; Aronov, B
Megjelenés: 2017.
Megjelent: (Füzetszám: 77, Oldalszám: 18:1-18:16)
H-free graphs, Independent Sets, and subexponential-time algorithms
Szerzők: Bacsó, Gábor; Marx, Dániel; Tuza, Zsolt
Szerkesztő: Guo, J; Hermelin, D
Megjelenés: 2017.
Megjelent: (Füzetszám: 63, Oldalszám: 3:1-3:12)
Hitting forbidden subgraphs in graphs of bounded treewidth
Szerzők: Cygan, M; Marx, Dániel; Pilipczuk, M; Pilipczuk, M
Megjelenés: 2017.
Megjelent: INFORMATION AND COMPUTATION (Kötetszám: 256, Oldalszám: 62-82)
Coloring Graphs with Constraints on Connectivity
Szerzők: Aboulker, P; Brettell, N; Havet, F; Marx, Dániel; Trotignon, N
Megjelenés: 2017.
Megjelent: JOURNAL OF GRAPH THEORY (Kötetszám: 85, Füzetszám: 4, Oldalszám: 814-838)

2016.

Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems
Szerzők: Marx, Dániel; Miltzow, Tillmann
Szerkesztő: Fekete, S; Lubiw, A
Megjelenés: 2016.
Megjelent: (Füzetszám: 51, Oldalszám: 52.1-52.16)
Parameterized vertex deletion problems for hereditary graph classes with a block property
Szerzők: Bonnet, Édouard; Brettel, Nick; Kwon, O-joung; Marx, Dániel
Megjelenés: 2016.
Megjelent: LECTURE NOTES IN ARTIFICIAL INTELLIGENCE (Kötetszám: 9941 L, Oldalszám: 233-244)
Routing with Congestion in Acyclic Digraphs
Szerzők: Amiri, S A; Kreutzer, S; Marx, Dániel; Rabinovich, R
Szerkesztő: Faliszewski, P; Muscholl, A; Niedermeier, R
Megjelenés: 2016.
Megjelent: (Oldalszám: 7:1-7:11)
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
Szerzők: Fomin, FV; Lokshtanov, D; Marx, Dániel; Pilipczuk, M; Pilipczuk, M
Megjelenés: 2016.
Megjelent: (Oldalszám: 515-524)
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
Szerzők: Curticapean, Radu; Marx, Dániel
Szerkesztő: Krauthgamer, R
Megjelenés: 2016.
Megjelent: (Füzetszám: 3, Oldalszám: 1650-1669)
Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
Szerzők: Kratsch, S; Marx, Dániel; Wahlstrom, M
Megjelenés: 2016.
Megjelent: ACM Transactions on Computation Theory (Kötetszám: 8, Füzetszám: 1, Oldalszám: 1)
A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
Szerzők: Bateni, M; Hajiaghayi, M; Demaine, ED; Marx, Dániel
Szerkesztő: Mansour, Y; Wichs, D
Megjelenés: 2016.
Megjelent: (Oldalszám: 570-583)
Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
Szerzők: Marx, Dániel; Salmasi, A; Sidiropoulos, A
Szerkesztő: Jansen, K; Mathieu, C; Rolim, JDP; Umans, C
Megjelenés: 2016.
Megjelent: (Füzetszám: 60, Oldalszám: 16:1-16:54)
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
Szerzők: Feldmann, Andreas Emil; Marx, Dániel
Szerkesztő: Chatzigiannakis, I
Megjelenés: 2016.
Megjelent: (Füzetszám: 55, Oldalszám: 27:1-27:14)
Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth.
Szerzők: Marx, Dániel; Mitsou, Valia
Szerkesztő: Chatzigiannakis, I
Megjelenés: 2016.
Megjelent: (Füzetszám: 55, Oldalszám: 28:1-28:15)
Fixed-Parameter Approximability of Boolean MinCSPs
Szerzők: Bonnet, Édouard; Egri, László; Marx, Dániel
Szerkesztő: Sankowski, P; Zaroliagis, C
Megjelenés: 2016.
Megjelent: (Oldalszám: 18:1-18:18)
On Problems as Hard as CNF-SAT
Szerzők: Cygan, M; Dell, H; Lokshtanov, D; Marx, Dániel; Nederlof, J
Megjelenés: 2016.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 12, Füzetszám: 3, Oldalszám: 41)
Chordal Editing is Fixed-Parameter Tractable
Szerzők: Cao, Yixin; Marx, Dániel
Megjelenés: 2016.
Megjelent: ALGORITHMICA (Kötetszám: 75, Füzetszám: 1, Oldalszám: 118-137)

2015.

Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Szerzők: Grohe, M; Marx, Dániel
Megjelenés: 2015.
Megjelent: SIAM JOURNAL ON COMPUTING (Kötetszám: 44, Füzetszám: 1, Oldalszám: 114-159)
An exact characterization of tractable demand patterns for maximum disjoint path problems
Szerzők: Marx, Dániel; Wollan, P
Szerkesztő: Piotr, Indyk
Megjelenés: 2015.
Megjelent: (Oldalszám: 642-661)
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
Szerzők: Marx, Dániel; Pilipczuk, M
Szerkesztő: Bansal, N; Finocchi, I
Megjelenés: 2015.
Megjelent: (Füzetszám: 9294, Oldalszám: 865-877)
Interval Deletion Is Fixed-Parameter Tractable
Szerzők: Cao, Y; Marx, Dániel
Megjelenés: 2015.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 11, Füzetszám: 3, Oldalszám: 21)
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
Szerzők: Chitnis, R; Cygan, M; Hajiaghayi, M; Marx, Dániel
Megjelenés: 2015.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 11, Füzetszám: 4, Oldalszám: a28)
Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation
Szerzők: Marx, Dániel; Végh, LA
Megjelenés: 2015.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 11, Füzetszám: 4, Oldalszám: a27)
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
Szerzők: Jansen, BMP; Marx, Dániel
Szerkesztő: Piotr, Indyk
Megjelenés: 2015.
Megjelent: (Füzetszám: 8845, Oldalszám: 616-629)

2014.

Minimizing movement: Fixed-parameter tractability
Szerzők: Demaine, Erik D.; Hajiaghayi, Mohammad T.; Marx, Dániel
Megjelenés: 2014.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 11, Füzetszám: 2, Oldalszám: 14)
Interval deletion is fixed-parameter tractable
Szerzők: Cao, Yixin; Marx, Dániel
Megjelenés: 2014.
Megjelent: (Oldalszám: 122-141)
Immersions in highly edge connected graphs
Szerzők: Marx, Dániel; Wollan, P
Megjelenés: 2014.
Megjelent: SIAM JOURNAL ON DISCRETE MATHEMATICS (Kötetszám: 28, Füzetszám: 1, Oldalszám: 503-520)
Parameterized complexity of Eulerian deletion problems
Szerzők: Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Schlotter, Ildikó Anna
Megjelenés: 2014.
Megjelent: ALGORITHMICA (Kötetszám: 68, Füzetszám: 1, Oldalszám: 41-61)
Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions)
Szerzők: Chitnis, R; Hajiaghayi, M; Marx, Dániel
Megjelenés: 2014.
Megjelent: (Oldalszám: 1782-1801)
A subexponential parameterized algorithm for Subset TSP on planar graphs
Szerzők: Klein, PN; Marx, Dániel
Megjelenés: 2014.
Megjelent: (Oldalszám: 1812-1830)
The limited blessing of low dimensionality: When 1-1/d is the best possible exponent for d-dimensional geometric problems
Szerzők: Marx, Dániel; Sidiropoulos, A
Megjelenés: 2014.
Megjelent: (Oldalszám: 67-76)
Hitting forbidden subgraphs in graphs of bounded treewidth
Szerzők: Cygan, Marek; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal
Megjelenés: 2014.
Megjelent: LECTURE NOTES IN COMPUTER SCIENCE (Kötetszám: 8635, Füzetszám: Part 2, Oldalszám: 189-200)
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
Szerzők: Marx, Dániel; Razgon, Igor
Megjelenés: 2014.
Megjelent: SIAM JOURNAL ON COMPUTING (Kötetszám: 43, Füzetszám: 2, Oldalszám: 355-388)
Constraint satisfaction parameterized by solution size
Szerzők: Bulatov, AA; Marx, Dániel
Megjelenés: 2014.
Megjelent: SIAM JOURNAL ON COMPUTING (Kötetszám: 43, Füzetszám: 2, Oldalszám: 573-616)
Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts
Szerzők: Curticapean, Radu; Marx, Dániel
Megjelenés: 2014.
Megjelent: (Oldalszám: 130-139)
Constraint solving via fractional edge covers
Szerzők: Grohe, M; Marx, Dániel
Megjelenés: 2014.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 11, Füzetszám: 1, Oldalszám: 4)
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
Szerzők: Marx, Dániel; Pilipczuk, Michal
Megjelenés: 2014.
Megjelent: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS (Kötetszám: 25, Oldalszám: 542-553)
Finding small patterns in permutations in linear time
Szerzők: Guillemot, Sylvain; Marx, Dániel
Megjelenés: 2014.
Megjelent: (Oldalszám: 82-101)
Exponential time complexity of the permanent and the Tutte polynomial
Szerzők: Dell, Holger; Husfeldt, Thore; Marx, Dániel; Taslaman, Nina; Wahlén, Martin
Megjelenés: 2014.
Megjelent: ACM TRANSACTIONS ON ALGORITHMS (Kötetszám: 10, Füzetszám: 4, Oldalszám: 21)
Chordal editing is fixed-parameter tractable
Szerzők: Marx, Dániel
Megjelenés: 2014.
Megjelent: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS (Kötetszám: 25, Oldalszám: 214-225)

2013.

List H-coloring a graph by removing few vertices
Szerzők: Chitnis, Rajesh; Egri, László; Marx, Dániel
Szerkesztő: Bodlaender, Hans L; Italiano, Giuseppe F
Megjelenés: 2013.
Megjelent: (Füzetszám: 8125, Oldalszám: 313-324)
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Szerzők: Marx, Dániel; Végh, LA
Szerkesztő: Fedor, V Fomin; Rūsiņš, Freivalds; Marta, Kwiatkowska; David, Peleg
Megjelenés: 2013.
Megjelent: (Füzetszám: 7965, Oldalszám: 721-732)
Block-sorted quantified conjunctive queries
Szerzők: Chen, Hubie; Marx, Dániel
Szerkesztő: Fedor, V Fomin; Rūsiņš, Freivalds; Marta, Kwiatkowska; David, Peleg
Megjelenés: 2013.
Megjelent: (Füzetszám: 7966, Oldalszám: 125-136)

Új keresés