2026-07-28T07:10:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22133 2024-12-04T06:53:43Z ddc:004 open_access

Dynamic Parameterized Problems on Unit Disk Graphs An, Shinwoo Cho, Kyungjin Jang, Leo Jung, Byeonghyeon Lee, Yudam Oh, Eunjin Shin, Donghun Shin, Hyeonjun Song, Chanho Unit disk graphs dynamic parameterized algorithms kernelization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shinwoo An and Kyungjin Cho and Leo Jang and Byeonghyeon Jung and Yudam Lee and Eunjin Oh and Donghun Shin and Hyeonjun Shin and Chanho Song 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.6 urn:nbn:de:0030-drops-221337 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.6 eng https://creativecommons.org/licenses/by/4.0/legalcode