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

Showing cs.DSShow all

6 papers · 1 filter

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…

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.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$ …