5 citations · 6 across the 13 of their papers we have counts for
8 papers · 1 filter
Spanning Paths and Cycles: Structural Limitations of the Irrelevant Vertex Technique
Dimitrios M. Thilikos, Sebastian Wiederrecht
The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the alg…
Finding irrelevant vertices in linear time on bounded-genus graphs
Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis +1
The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these probl…
Dynamic programming on bipartite tree decompositions
Lars Jaffke, Laure Morelle, Ignasi Sau +1
We revisit a graph width parameter that we dub bipartite treewidth (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal numb…
H-Planarity and Parametric Extensions: when Modulators Act Globally
Fedor V. Fomin, Petr A. Golovach, Laure Morelle +1
We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend…
Graph modification of bounded size to minor-closed classes as fast as vertex deletion
Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
A replacement action is a function that maps each graph to a collection of graphs of size at most . Given a graph class , we consider a gener…
A Constant-factor Approximation for Weighted Bond Cover
Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos
The Weighted -Vertex Deletion for a class of graphs asks, weighted graph , for a minimum weight vertex set such that The case when…