Lower Bounds on Tree Covers
SIAM Journal on Computing · 31.08.2026 · 55 (4) · 578-591
DOI: 10.1137/25m1834077 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 23.07.2026. Verfasst von Yu Chen und 2 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
Given an [Formula: see text]-point metric space [Formula: see text], a tree cover [Formula: see text] is a set of [Formula: see text] trees on [Formula: see text] such that every pair of vertices in [Formula: see text] has a low-distortion path in one of the trees in [Formula: see text]. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size [Formula: see text] and distortion. When [Formula: see text], the best distortion is known to be [Formula: see text]. For a constant [Formula: see text], the best distortion upper bound is [Formula: see text] and the strongest lower bound is [Formula: see text], leaving a gap to be closed. In this paper, we improve the lower bound to [Formula: see text]. Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Chen, Y., Tan, Z., & Xu, H. (2026). Lower Bounds on Tree Covers. SIAM Journal on Computing, 55(4), 578-591. https://doi.org/10.1137/25m1834077
Vancouver
Chen Y, Tan Z, Xu H. Lower Bounds on Tree Covers. SIAM Journal on Computing. 2026;55(4):578-591. doi:10.1137/25m1834077
BibTeX
@article{Chen2026,
author = {Chen, Yu and Tan, Zihan and Xu, Hangyu},
title = {Lower Bounds on Tree Covers},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {4},
pages = {578--591},
doi = {10.1137/25m1834077}
}
EUVIMED