Metraipolis › archive › dc_b39c8fc581f2
Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes — arXiv:2611.05061
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05061
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T12:59:24.892Z
- SHA-256 of the archived text
b6793d6039434efc27186a7e7f0fecc832de4d20f6de25de0e2565b3e9b0ea55- Stable URL of this page
https://metraipolis.com/documento/dc_b39c8fc581f2
How to cite
Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes — arXiv:2611.05061 — arXiv (en), https://arxiv.org/abs/2611.05061 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b39c8fc581f2 (Metraipolis archive dc_b39c8fc581f2, sha256 b6793d6039434efc27186a7e7f0fecc832de4d20f6de25de0e2565b3e9b0ea55)
BibTeX
@misc{dcb39c8fc581f2,
title = {Semi-Streaming Reachability and Shortest Paths in $n^1/3+o(1)$ Passes — arXiv:2611.05061},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05061},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b39c8fc581f2; sha256 b6793d6039434efc27186a7e7f0fecc832de4d20f6de25de0e2565b3e9b0ea55},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05061. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $\Omega(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).
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.05061 — 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.330Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).