Dániel Marx
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Dániel Marx has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Ken-Ichi Kawarabayashi
National Institute of Informatics The University of Tokyo Tokyo Japan
1 shared publication - Martin Grohe
RWTH Aachen University, Aachen, Germany
1 shared publication - Paul Wollan
Department of Computer Science University of Rome "La Sapienza" Rome Italy
1 shared publication
Latest Publications
- Open Access
Finding topological subgraphs is fixed-parameter tractable
We show that for every fixed undirected graph $H$, there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$, if $G$ contains $H$ as a topological subgraph (that is, a subdivision of $H$ is subgraph of $G$). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every $H$ we obtain an $O(|V(G)|^3)$ time algorithm that tests if there is an immersion of $H$ into a given graph $G$. This answers another open question raised by Downey and Fellows in 1992.Open AccessFinding topological subgraphs is fixed-parameter tractable
We show that for every fixed undirected graph $H$, there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$, if $G$ contains $H$ as a topological subgraph (that is, a subdivision of $H$ is subgraph of $G$). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every $H$ we obtain an $O(|V(G)|^3)$ time algorithm that tests if there is an immersion of $H$ into a given graph $G$. This answers another open question raised by Downey and Fellows in 1992. - 31 January 2008
- Published by Elsevier in Operations Research Letters
- Vol. 36 (1) , 31-36
Searching the k-change neighborhood for TSP is W[1]-hard
- 31 January 2008
- Published by Elsevier in Operations Research Letters
- Vol. 36 (1) , 31-36
Searching the k-change neighborhood for TSP is W[1]-hard
- Top Cited Papers
- 6 March 2007
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 51 (1) , 60-78
Parameterized Complexity and Approximation Algorithms
Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.
- 6 March 2007
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 51 (1) , 60-78
Top Cited PapersParameterized Complexity and Approximation Algorithms
Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research.