29 citations · 63 across the 22 of their papers we have counts for
4 papers · 1 filter
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…