38 citations · 189 across the 43 of their papers we have counts for
8 papers · 1 filter
Complexity and algorithms for constant diameter augmentation problems
Eun Jung Kim, Martin Milanic, Jérôme Monnot +1
We study the following problem: for given integers and graph , can we obtain a graph with diameter via at most edge deletions ? We determine the computational comp…
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
Jungho Ahn, Eun Jung Kim, Euiwoong Lee
For a family of graphs , Weighted -Deletion is the problem for which the input is a vertex weighted graph and the goal is to delete $S\subseteq…
On the tree-width of even-hole-free graphs
Pierre Aboulker, Isolde Adler, Eun Jung Kim +2
The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, )-free graphs was constructed, that still…
Grundy Distinguishes Treewidth from Pathwidth
Rémy Belmonte, Eun Jung Kim, Michael Lampis +2
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to und…
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time for -vertex graphs given with a witness that th…
Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim +2
The twin-width of a graph is the minimum integer such that has a -contraction sequence, that is, a sequence of iterated vertex identifications for which t…