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

CREATORReilly Browne, Hsien-Chih Chang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61530
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00219

Browse the full library · About the Tower of Babel