1 citations · 1 across the 5 of their papers we have counts for
10 papers
Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting
Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht
We study the \textsc{-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph with vertices and vertex pairs embedded on a s…
Deterministic Distance Approximation in MPC via Improved Hitting Sets
Kyungjin Cho, Michal Dory, Yannic Maus +1
In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we si…
Dynamic parameterized problems on unit disk graphs
Shinwoo An, Kyungjin Cho, Leo Jang +6
In this paper, we study fundamental parameterized problems such as -Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk…
Mimicking Networks for Constrained Multicuts in Hypergraphs
Kyungjin Cho, Eunjin Oh
In this paper, we study a \emph{multicut-mimicking network} for a hypergraph over terminals with a parameter . It is a hypergraph preserving the minimum multicut values of a…
Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
Shinwoo An, Yeonsu Chang, Kyungjin Cho +4
Horiyama et al. (AAAI 2024) considered the problem of generating instances with a unique minimum vertex cover under certain conditions. The Minimum Pre-assignment for Uniquificatio…
Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners
Kyungjin Cho, Jihun Shin, Eunjin Oh
In this paper, we present approximate distance and shortest-path oracles for fault-tolerant Euclidean spanners motivated by the routing problem in real-world road networks. An -…
Faster Algorithms for Cycle Hitting Problems on Disk Graphs
Shinwoo An, Kyungjin Cho, Eunjin Oh
In this paper, we consider three hitting problems on a disk intersection graph: Triangle Hitting Set, Feedback Vertex Set, and Odd Cycle Transversal. Given a disk intersection grap…
Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in and Linear in
Kyungjin Cho, Eunjin Oh, Seunghyeok Oh
In this paper, we study the \textsf{Planar Disjoint Paths} problem: Given an undirected planar graph with vertices and a set of pairs of vertice…
Linear-Time Approximation Scheme for k-Means Clustering of Affine Subspaces
Kyungjin Cho, Eunjin Oh
In this paper, we present a linear-time approximation scheme for -means clustering of \emph{incomplete} data points in -dimensional Euclidean space. An \emph{incomplete} data…
Optimal Algorithm for the Planar Two-Center Problem
Kyungjin Cho, Eunjin Oh, Haitao Wang +1
We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set of points in the plane and the goal is to find…