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
| CREATOR | Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22669