Metraipolis › archive › dc_6cfe0bc86fef

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners — arXiv:2611.04731

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04731
License (as archived)
CC0-1.0
Archived
2026-11-04T12:59:15.222Z
SHA-256 of the archived text
4b563d7291ecc9e99ac180f5326a1fafb562c0fb172cda93eddded8b187e8d15
Stable URL of this page
https://metraipolis.com/documento/dc_6cfe0bc86fef

How to cite

Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners — arXiv:2611.04731 — arXiv (en), https://arxiv.org/abs/2611.04731 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6cfe0bc86fef (Metraipolis archive dc_6cfe0bc86fef, sha256 4b563d7291ecc9e99ac180f5326a1fafb562c0fb172cda93eddded8b187e8d15)
BibTeX
@misc{dc6cfe0bc86fef,
  title = {Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners — arXiv:2611.04731},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04731},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6cfe0bc86fef; sha256 4b563d7291ecc9e99ac180f5326a1fafb562c0fb172cda93eddded8b187e8d15},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04731. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.04731 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:35:02.310Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).