1 citations · 1 across the 5 of their papers we have counts for
6 papers · 1 filter
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…
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…