89 citations · 484 across the 68 of their papers we have counts for
6 papers · 2 filters
The limited blessing of low dimensionality: when is the best possible exponent for -dimensional geometric problems
Dániel Marx, Anastasios Sidiropoulos
We are studying -dimensional geometric problems that have algorithms with appearing in the exponent of the running time, for example, in the form of or $…
Subexponential parameterized algorithms for graphs of polynomial growth
Dániel Marx, Marcin Pilipczuk
We show that for a number of parameterized problems for which only time algorithms are known on general graphs, subexponential parameterized algorithms with run…
Routing with Congestion in Acyclic Digraphs
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx +1
We study the version of the -disjoint paths problem where demand pairs , , are specified in the input and the paths in the solution are allowed…
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx +3
We prove the following theorem. Given a planar graph and an integer , it is possible in polynomial time to randomly sample a subset of vertices of with the following…
Parameterized vertex deletion problems for hereditary graph classes with a block property
Édouard Bonnet, Nick Brettell, O-joung Kwon +1
For a class of graphs , the Bounded -Block Vertex Deletion problem asks, given a graph on vertices and positive integers and , whether ther…
Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs
Daniel Marx, Ario Salmasi, Anastasios Sidiropoulos
In the Asymmetric Traveling Salesperson Problem (ATSP) the goal is to find a closed walk of minimum cost in a directed graph visiting every vertex. We consider the approximability…