121 citations · 360 across the 111 of their papers we have counts for
4 papers · 1 filter
Hitting forbidden minors: Approximation and Kernelization
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra +2
We study a general class of problems called F-deletion problems. In an F-deletion problem, we are asked whether a subset of at most vertices can be deleted from a graph suc…
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal
Daniel Lokshtanov, Dániel Marx, Saket Saurabh
We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothe…
Bidimensionality and EPTAS
Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman +1
Bidimensionality theory is a powerful framework for the development of metaalgorithmic techniques. It was introduced by Demaine et al. as a tool to obtain sub-exponential time para…
Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs
Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov +2
We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied p…