Search Results

Documents authored by Cho, Kyungjin

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.6
Dynamic Parameterized Problems on Unit Disk Graphs

Authors: Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In this paper, we study fundamental parameterized problems such as k-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs. Given a vertex set V changing dynamically under vertex insertions and deletions, our goal is to maintain data structures so that the aforementioned parameterized problems on the unit disk graph induced by V can be solved efficiently. Although dynamic parameterized problems on general graphs have been studied extensively, no previous work focuses on unit disk graphs. In this paper, we present the first data structures for fundamental parameterized problems on dynamic unit disk graphs. More specifically, our data structure supports 2^O(√k) update time and O(k) query time for k-Path/Cycle. For the other problems, our data structures support O(log n) update time and 2^O(√k) query time, where k denotes the output size.
Cite as

Shinwoo An, Kyungjin Cho, Leo Jang, Byeonghyeon Jung, Yudam Lee, Eunjin Oh, Donghun Shin, Hyeonjun Shin, and Chanho Song. Dynamic Parameterized Problems on Unit Disk Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2024.6,
  author =	{An, Shinwoo and Cho, Kyungjin and Jang, Leo and Jung, Byeonghyeon and Lee, Yudam and Oh, Eunjin and Shin, Donghun and Shin, Hyeonjun and Song, Chanho},
  title =	{{Dynamic Parameterized Problems on Unit Disk Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.6},
  URN =		{urn:nbn:de:0030-drops-221337},
  doi =		{10.4230/LIPIcs.ISAAC.2024.6},
  annote =	{Keywords: Unit disk graphs, dynamic parameterized algorithms, kernelization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.21
Mimicking Networks for Constrained Multicuts in Hypergraphs

Authors: Kyungjin Cho and Eunjin Oh

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In this paper, we study a multicut-mimicking network for a hypergraph over terminals T with a parameter c. It is a hypergraph preserving the minimum multicut values of any set of pairs over T where the value is at most c. This is a new variant of the multicut-mimicking network of a graph in [Wahlström ICALP'20], which introduces a parameter c and extends it to handle hypergraphs. Additionally, it is a natural extension of the connectivity-c mimicking network introduced by [Chalermsook et al. SODA'21] and [Jiang et al. ESA'22] that is a (hyper)graph preserving the minimum cut values between two subsets of terminals where the value is at most c. We propose an algorithm for a hypergraph that returns a multicut-mimicking network over terminals T with a parameter c having |T|c^O(rlog c) hyperedges in p^{1+o(1)} + |T|(c^rlog n)^{Õ(rc)}⋅m time, where p and r are the total size and the rank, respectively, of the hypergraph.
Cite as

Kyungjin Cho and Eunjin Oh. Mimicking Networks for Constrained Multicuts in Hypergraphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.ISAAC.2024.21,
  author =	{Cho, Kyungjin and Oh, Eunjin},
  title =	{{Mimicking Networks for Constrained Multicuts in Hypergraphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.21},
  URN =		{urn:nbn:de:0030-drops-221487},
  doi =		{10.4230/LIPIcs.ISAAC.2024.21},
  annote =	{Keywords: hyperedge multicut, vertex sparsification, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.40
Optimal Algorithm for the Planar Two-Center Problem

Authors: Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set S of n points in the plane and the goal is to find two smallest congruent disks whose union contains all points of S. A longstanding open problem has been to obtain an O(nlog n)-time algorithm for planar two-center, matching the Ω(nlog n) lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in O(nlog² n) time. In this paper, we present an O(nlog n)-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
Cite as

Kyungjin Cho, Eunjin Oh, Haitao Wang, and Jie Xue. Optimal Algorithm for the Planar Two-Center Problem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.SoCG.2024.40,
  author =	{Cho, Kyungjin and Oh, Eunjin and Wang, Haitao and Xue, Jie},
  title =	{{Optimal Algorithm for the Planar Two-Center Problem}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.40},
  URN =		{urn:nbn:de:0030-drops-199857},
  doi =		{10.4230/LIPIcs.SoCG.2024.40},
  annote =	{Keywords: two-center, r-coverage, disk coverage, circular hulls}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.46
Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces

Authors: Kyungjin Cho and Eunjin Oh

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In this paper, we present a linear-time approximation scheme for k-means clustering of incomplete data points in d-dimensional Euclidean space. An incomplete data point with Δ > 0 unspecified entries is represented as an axis-parallel affine subspace of dimension Δ. The distance between two incomplete data points is defined as the Euclidean distance between two closest points in the axis-parallel affine subspaces corresponding to the data points. We present an algorithm for k-means clustering of axis-parallel affine subspaces of dimension Δ that yields an (1+ε)-approximate solution in O(nd) time. The constants hidden behind O(⋅) depend only on Δ, ε and k. This improves the O(n² d)-time algorithm by Eiben et al. [SODA'21] by a factor of n.
Cite as

Kyungjin Cho and Eunjin Oh. Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cho_et_al:LIPIcs.ISAAC.2021.46,
  author =	{Cho, Kyungjin and Oh, Eunjin},
  title =	{{Linear-Time Approximation Scheme for k-Means Clustering of Axis-Parallel Affine Subspaces}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.46},
  URN =		{urn:nbn:de:0030-drops-154794},
  doi =		{10.4230/LIPIcs.ISAAC.2021.46},
  annote =	{Keywords: k-means clustering, affine subspaces}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact