6 citations · 14 across the 31 of their papers we have counts for
4 papers · 1 filter
Lossy Kernels for Connected Dominating Set on Sparse Graphs
Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad +2
For , an -approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance of a problem and outputs an instance (of…
Rank Vertex Cover as a Natural Problem for Algebraic Compression
Syed Mohammad Meesum, Fahad Panolan, Saket Saurabh +1
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem has been a longstanding, notorious open problem in Parameterized Complexity. Five y…
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a -degenerate graph…
Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
We give algorithms with running time for the following problems. Given an -vertex unit disk graph and an integer , decide whethe…