ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929281184038912 |
|---|---|
| author | An, Shinwoo Oh, Eunjin |
| author_facet | An, Shinwoo Oh, Eunjin |
| contents | In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set of $k$ vertex-disjoint cycles of G if it exists. Our algorithm runs in time $2^{O(\sqrt k)}n^{O(1)}$. This improves the $2^{O(\sqrt k\log k)}n^{O(1)}$-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_11426 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs An, Shinwoo Oh, Eunjin Data Structures and Algorithms Computational Geometry In this paper, we consider the Cycle Packing problem on unit disk graphs defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set of $k$ vertex-disjoint cycles of G if it exists. Our algorithm runs in time $2^{O(\sqrt k)}n^{O(1)}$. This improves the $2^{O(\sqrt k\log k)}n^{O(1)}$-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. |
| title | ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/2403.11426 |