20 citations · 180 across the 43 of their papers we have counts for
18 papers · 1 filter
A new width parameter of graphs based on edge cuts: -edge-crossing width
Yeonsu Chang, O-joung Kwon, Myounghwan Lee
We introduce graph width parameters, called -edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decompos…
Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
Jungho Ahn, Jinha Kim, O-joung Kwon
Let be a family of graphs, and let be nonnegative integers. The \textsc{-Covering} problem asks whether for a graph and an integer , t…
A Unifying Framework for Characterizing and Computing Width Measures
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specifi…
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 polynomial kernel for -leaf power deletion
Jungho Ahn, Eduard Eiben, O-joung Kwon +1
For a non-negative integer , the -leaf power of a tree is a simple graph on the leaves of such that two vertices are adjacent in if and only if their di…
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Eduard Eiben, Robert Ganian, Thekla Hamm +1
We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess ot…
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…
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…
A Polynomial Kernel for Distance-Hereditary Vertex Deletion
Eun Jung Kim, O-joung Kwon
A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the origina…
A width parameter useful for chordal and co-comparability graphs
Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme +1
We investigate new graph classes of bounded mim-width, strictly extending interval graphs and permutation graphs. The graphs and are graphs…
A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion
Eduard Eiben, Robert Ganian, O-joung Kwon
Vertex deletion problems ask whether it is possible to delete at most vertices from a graph so that the resulting graph belongs to a specified graph class. Over the past years,…
Parameterized vertex deletion problems for hereditary graph classes with a block property
Édouard Bonnet, Nick Brettell, O-joung Kwon +1
For a class of graphs , the Bounded -Block Vertex Deletion problem asks, given a graph on vertices and positive integers and , whether ther…
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
The maximum common subtree isomorphism problem asks for the largest possible isomorphism between subtrees of two given input trees. This problem is a natural restriction of the max…
A polynomial kernel for Block Graph Deletion
Eun Jung Kim, O-joung Kwon
In the Block Graph Deletion problem, we are given a graph on vertices and a positive integer , and the objective is to check whether it is possible to delete at most …
An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion
Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon +1
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006].…