Eun Jung Kim

collaborators

3 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 $(I^\pm_{G W} + ε)$ -approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $I^\pm_{G W} \approx 0.878$ is the…

cs.DS2025

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 $I ¨ $ from $V (G)$ to ${1, \dots, ∣ V (G) ∣}$ such that $\max_{\{u, v \} \in E(G)} | Ï(u) - Ï(…