121 citations · 373 across the 96 of their papers we have counts for
5 papers · 1 filter
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov +6
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for…
Outlier Detection for DNA Fragment Assembly
Christina Boucher, Christine Lo, Daniel Lokshtanov
Given length- strings over a constant size alphabet together with parameters and , the objective in the {\em Consensus String with Outli…
Bidimensionality and Geometric Graphs
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh
In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on…
Contracting Graphs to Paths and Trees
Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque +2
Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and…
Obtaining a Bipartite Graph by Contracting Few Edges
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov +1
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph and an integer , and the ta…