13 citations · 48 across the 11 of their papers we have counts for
9 papers · 1 filter
Fast Biclustering by Dual Parameterization
Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil +1
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We sho…
Kernelization and Sparseness: the case of Dominating Set
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin +9
We prove that for every positive integer and for every graph class of bounded expansion, the -Dominating Set problem admits a linear kernel on graphs from $\mat…
A Faster Parameterized Algorithm for Treedepth
Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil +1
The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence o…
Kernelization Using Structural Parameters on Sparse Graph Classes
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +5
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs…
Linear kernels and single-exponential algorithms via protrusion decompositions
Eun Jung Kim, Alexander Langer, Christophe Paul +4
A \emph{-treewidth-modulator} of a graph is a set such that the treewidth of is at most some constant . In this paper, we present a novel algor…
Linear Kernels on Graphs Excluding Topological Minors
Alexander Langer, Felix Reidl, Peter Rossmanith +1
We show that problems which have finite integer index and satisfy a requirement we call treewidth-bounding admit linear kernels on the class of -topological-minor free graphs, f…