121 citations · 373 across the 96 of their papers we have counts for
5 papers · 1 filter
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan +2
We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized comp…
Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh +1
We give the first linear kernels for the (Connected) Dominating Set problems on H-topological minor free graphs. We prove the existence of polynomial time algorithms that, for a gi…
SeeSite: Efficiently Finding Co-occurring Splice Sites and Exon Splicing Enhancers
Christine Lo, Boyko Kakaradov, Daniel Lokshtanov +1
The problem of identifying splice sites consists of two sub-problems: finding their boundaries, and characterizing their sequence markers. Other splicing elements---including, enha…
Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms
Fedor Fomin, Daniel Lokshtanov, Neeldhara Misra +1
Let F be a finite set of graphs. In the F-Deletion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G s…
Faster Parameterized Algorithms using Linear Programming
Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman +2
We investigate the parameterized complexity of Vertex Cover parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) re…