13 citations · 26 across the 7 of their papers we have counts for
11 papers
A practical fpt algorithm for Flow Decomposition and transcript assembly
Kyle Kloster, Philipp Kuinke, Michael P. O'Brien +4
The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transc…
Width, depth and space
Li-Hsuan Chen, Felix Reidl, Peter Rossmanith +1
The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of inter…
Characterising Bounded Expansion by Neighbourhood Complexity
Felix Reidl, Fernando Sánchez Villaamil, Konstantinos Stavropoulos
We show that a graph class has bounded expansion if and only if it has bounded -neighbourhood complexity, i.e. for any vertex set of any subgraph of $G\in\cal G…
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…
Zig-Zag Numberlink is NP-Complete
Aaron Adcock, Erik D. Demaine, Martin L. Demaine +4
When can terminal pairs in an grid be connected by vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our ha…
Hyperbolicity, degeneracy, and expansion of random intersection graphs
Matthew Farrell, Timothy Goodrich, Nathan Lemons +3
We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks wh…
Structural Sparsity of Complex Networks: Bounded Expansion in Random Models and Real-World Graphs
Erik D. Demaine, Felix Reidl, Peter Rossmanith +3
This research establishes that many real-world networks exhibit bounded expansion, a strong notion of structural sparsity, and demonstrates that it can be leveraged to design effic…
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…
Black-and-white threshold graphs
Ling-Ju Hung, Ton Kloks, Fernando Villaamil
Let k be a natural number. We introduce k-threshold graphs. We show that there exists an O(n^3) algorithm for the recognition of k-threshold graphs for each natural number k. k-Thr…