Computing Dominating Sets in Disk Graphs with Centers in Convex Position
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915762346655744 |
|---|---|
| author | Tkachenko, Anastasiia Wang, Haitao |
| author_facet | Tkachenko, Anastasiia Wang, Haitao |
| contents | Given a set $P$ of $n$ points in the plane and a collection of disks centered at these points, the disk graph $G(P)$ has vertex set $P$, with an edge between two vertices if their corresponding disks intersect. We study the dominating set problem in $G(P)$ under the special case where the points of $P$ are in convex position. The problem is NP-hard in general disk graphs. Under the convex position assumption, however, we present the first polynomial-time algorithm for the problem. Specifically, we design an $O(k^2 n \log^2 n)$-time algorithm, where $k$ denotes the size of a minimum dominating set. For the weighted version, in which each disk has an associated weight and the goal is to compute a dominating set of minimum total weight, we obtain an $O(n^5 \log^2 n)$-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22609 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing Dominating Sets in Disk Graphs with Centers in Convex Position Tkachenko, Anastasiia Wang, Haitao Computational Geometry Data Structures and Algorithms Given a set $P$ of $n$ points in the plane and a collection of disks centered at these points, the disk graph $G(P)$ has vertex set $P$, with an edge between two vertices if their corresponding disks intersect. We study the dominating set problem in $G(P)$ under the special case where the points of $P$ are in convex position. The problem is NP-hard in general disk graphs. Under the convex position assumption, however, we present the first polynomial-time algorithm for the problem. Specifically, we design an $O(k^2 n \log^2 n)$-time algorithm, where $k$ denotes the size of a minimum dominating set. For the weighted version, in which each disk has an associated weight and the goal is to compute a dominating set of minimum total weight, we obtain an $O(n^5 \log^2 n)$-time algorithm. |
| title | Computing Dominating Sets in Disk Graphs with Centers in Convex Position |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.22609 |