Eun Jung Kim

activity

20152026

most citedFlow-augmentation II: Undirected graphs

1 citations · 1 across the 8 of their papers we have counts for

collaborators

8 papers

cs.DS2026

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications

Édouard Bonnet, Colin Geniet, Eun Jung Kim +1

A signed tree model of a graph $G$ is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of $G$ , together with 2-colo…

cs.DS2025

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson

Jungho Ahn, Ian DeHaan, Eun Jung Kim +1

We present a polynomial-time $(α_{G W} + ε)$ -approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{G W} \approx 0.878$ is the a…

math.CO2024

Shallow vertex minors, stability, and dependence

H. Buffière, E. Kim, P. Ossona de Mendez

Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, a…

cs.DS2023

Bandwidth Parameterized by Cluster Vertex Deletion Number

Tatsuya Gima, Eun Jung Kim, Noleen Köhler +2

Given a graph $G$ and an integer $b$ , Bandwidth asks whether there exists a bijection $π$ from $V (G)$ to ${1, \dots, ∣ V (G) ∣}$ such that $\max_{\{u, v \} \in E(G)} | π(u) - π(v)…

cs.CC2023

Representing Matroids over the Reals is $\exists R$ -complete

Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow

A matroid $M$ is an ordered pair $(E, I)$ , where $E$ is a finite set called the ground set and a collection $I \subset 2^{E}$ called the independent sets which satisfy the conditions…

cs.DS2021

Flow-augmentation I: Directed graphs

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph $G$ , two vertices $s, t \in V (G)$ , and an…

cs.DS2020★ 1 cited

Flow-augmentation II: Undirected graphs

Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1

We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph $G$ with distinguished vertices $s, t \in V (G)$ and an intege…

cs.DS2015

Recognizing k-equistable graphs in FPT time

Eun Jung Kim, Martin Milanic, Oliver Schaudt

A graph $G = (V, E)$ is called equistable if there exist a positive integer $t$ and a weight function $w : V \to N$ such that $S \subseteq V$ is a maximal stable set of $G$ …