20 citations · 180 across the 43 of their papers we have counts for
8 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…
Erdős-Pósa property of chordless cycles and its applications
Eun Jung Kim, O-joung Kwon
A chordless cycle, or equivalently a hole, in a graph is an induced subgraph of which is a cycle of length at least . We prove that the Erdős-Pósa property holds for cho…
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^…
Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
Édouard Bonnet, Nick Brettell, O-joung Kwon +1
It has long been known that Feedback Vertex Set can be solved in time on -vertex graphs of treewidth , but it was only recently t…
On low rank-width colorings
O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz
We introduce the concept of low rank-width colorings, generalising the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with boun…
Chi-boundedness of graph classes excluding wheel vertex-minors
Hojin Choi, O-joung Kwon, Sang-il Oum +1
A class of graphs is -bounded if there exists a function such that for every graph in the class and an induced subgraph of , if …
An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-joung Kwon
In this paper, we prove that, given a clique-width -expression of an -vertex graph, \textsc{Hamiltonian Cycle} can be solved in time . This improves the n…