20 citations · 180 across the 43 of their papers we have counts for
6 papers · 1 filter
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
Tree pivot-minors and linear rank-width
Konrad K. Dabrowski, François Dross, Jisu Jeong +4
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~, the class…
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…
A half-integral Erdős-Pósa theorem for directed odd cycles
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon +1
We prove that there exists a function such that every directed graph contains either directed odd cycles where every vertex of is c…
Well-partitioned chordal graphs: obstruction set and disjoint paths
Jungho Ahn, Lars Jaffke, O-joung Kwon +1
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the ve…
Rainbow independent sets on dense graph classes
Jinha Kim, Minki Kim, O-joung Kwon
Given a family of independent sets in a graph, a rainbow independent set is an independent set such that there is an injection where fo…