Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than · 2025

Read Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs by Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than (2025) 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-2503-22669.txt.

Description

Hsien-Chih Chang and co-authors settle a long open question about covering graphs with a few light trees, in a paper from 2025. A tree cover lets every pair of points find a near-shortest path inside one of a few trees. Past covers kept the total weight high, growing with the size of the graph. Whether a constant-weight cover exists was unknown, even for flat point sets.

Their answer is yes for doubling graphs, where balls grow at a tame rate. They build a spanning tree cover that uses only edges of the graph itself. It needs just a fixed count of trees at near-perfect stretch. From it flow a light tree cover, a compact routing scheme, and a distance oracle that reports paths. The result closes a question open since the mid-1990s.

Catalog record

CREATORHsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22669

Browse the full library · About the Tower of Babel