Trading off space for passes in graph streaming problems

DOI10.1145/1644015.1644021zbMath1300.68072OpenAlexW1967521717MaRDI QIDQ5891890

Camil Demetrescu, Irene Finocchi, Andrea Ribichini

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1644015.1644021

zbMATH Keywords

shortest pathsgraph connectivitydata streaming

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (6)

An external-memory algorithm for string graph construction ⋮ Graph Connectivity in Log Steps Using Label Propagation ⋮ Adapting parallel algorithms to the W-stream model, with applications to graph problems ⋮ Streaming graph computations with a helpful advisor ⋮ A one pass streaming algorithm for finding Euler tours ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

This page was built for publication: Trading off space for passes in graph streaming problems