Better Bounds for Semi-Streaming Single-Source Shortest Paths
In the semi-streaming model, an algorithm must process any $n$-vertex graph by making one or few passes over a stream of its edges, use $O(n \cdot \text{polylog }n)$ words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest path...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2507.17841 http://arxiv.org/abs/2507.17841 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
Ejemplares similares: Better Bounds for Semi-Streaming Single-Source Shortest Paths
- Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings
- (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
- Covering Approximate Shortest Paths with DAGs
- Coloring Graphs with Few Colors in the Streaming Model
- A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
- Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints