Trading off space for passes in graph streaming problems

DOI10.1145/1644015.1644021MaRDI QIDQ5891890zbMATH OpenOpenAlexFDO

Authors 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

data streaminggraph connectivityshortest paths

Mathematics Subject Classification ID

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

Recommendations

• Graph distances in the streaming model: the value of space
• Graph Distances in the Data-Stream Model
• Automata, Languages and Programming
• On graph problems in a semi-streaming model
• Dynamic graph stream algorithms in \(o(n)\) space

Cited in

(12)

• Space lower bounds for graph stream problems
• An external-memory algorithm for string graph construction
• Streamed Graph Drawing and the File Maintenance Problem
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Superlinear lower bounds for multipass graph processing
• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Graph connectivity in log steps using label propagation
• A one pass streaming algorithm for finding Euler tours
• Streaming edge coloring with asymptotically optimal colors
• Low-memory algorithms for online edge coloring
• Improved streaming edge coloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891890)