Parameterized Algorithms for Computing r-Scattered Sets and r-Dominating Sets on Unit Disk Graphs
- Title
- Parameterized Algorithms for Computing r-Scattered Sets and r-Dominating Sets on Unit Disk Graphs
- Authors
- 신지훈
- Date Issued
- 2024
- Publisher
- 포항공과대학교
- Abstract
- We study the r-scattered set problem and the r-dominating set problem defined on the unit disk graph on the 2-dimensional Euclidean plane. They are the generalized version of the independent set problem and the dominating set problem, respectively. Our main result is that the r-scattered set problem on the unit disk graph can be solved in n^O(k) time. Also, we show that the r-dominating set problem on the unit disk graph can be solved in n^O(k) time if the input graph has a unique-neighbored r-dominating set of size k. The algorithm is based on the concept of partitioning the plane with a hypothetical solution of k vertices. It is known that there exists a closed curve separating the solution vertices in a balanced manner if the degree of every vertex in the partition is three. Then it is possible to guess the correct solution by listing the balanced separators of the partition to obtain subproblems of balanced size.
- URI
- http://postech.dcollection.net/common/orgView/200000736296
https://oasis.postech.ac.kr/handle/2014.oak/123351
- Article Type
- Thesis
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.