19 citations · 218 across the 100 of their papers we have counts for
4 papers · 1 filter
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…
Hardness of approximation for strip packing
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk +1
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing…
Approximation and Kernelization for Chordal Vertex Deletion
Bart M. P. Jansen, Marcin Pilipczuk
The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel f…
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…