5 citations · 11 across the 5 of their papers we have counts for
5 papers
A note on the complexity of Feedback Vertex Set parameterized by mim-width
Lars Jaffke, O-joung Kwon, Jan Arne Telle
We complement the recent algorithmic result that Feedback Vertex Set is XP-time solvable parameterized by the mim-width of a given branch decomposition of the input graph [3] by sh…
A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width
Lars Jaffke, O-joung Kwon, Jan Arne Telle
We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decompositi…
Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width
Lars Jaffke, O-joung Kwon, Jan Arne Telle
We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give $n^…
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
Lars Jaffke, Bart M. P. Jansen
The -Coloring problem asks whether the vertices of a graph can be properly colored with colors. Lokshtanov et al. [SODA 2011] showed that -Coloring on graphs with a feedb…
MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree -Outerplanar Graphs
Lars Jaffke, Hans L. Bodlaender
One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in…