EUVIMEDEUVIMED entdecken
Crossref

Lower Bounds on Tree Covers

Yu Chen, Zihan Tan, Hangyu Xu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →