DROPS

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}
}

Search Results

Documents authored by Song, Chanho

Dynamic Parameterized Problems on Unit Disk Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message