5 papers
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…
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…
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…
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…