Single-Criteria Metric r r -Dominating Set Problem via Minor-Preserving Support
Reilly Browne, Hsien-Chih Chang · 2026
Read Single-Criteria Metric r r -Dominating Set Problem via Minor-Preserving Support by Reilly Browne, Hsien-Chih Chang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00219.txt.
Description
Browne and Chang give the first constant-factor approximation in polynomial time for vertex-weighted metric r-dominating sets on planar graphs, for any r. Earlier bicriteria methods let radius and weight overshoot slightly. Their algorithm samples quasi-uniformly, bounding cell complexity of radius-r balls to linear in vertex count. Two innovations drive it. A support graph built as contractions of Voronoi cells comes first. Each deep cell goes to a unique triple of ball centers, so counting reduces to depth-3 cells, proven linear geometrically.
Catalog record
| CREATOR | Reilly Browne, Hsien-Chih Chang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61530 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00219