Adapting parallel algorithms to the W-stream model, with applications to graph problems

DOI10.1016/j.tcs.2010.08.030zbMath1234.68458MaRDI QIDQ410728

Camil Demetrescu, Gabriel Moruz, Andrea Ribichini, Bruno Escoffier

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.030

zbMATH Keywords

data streaming model; graph problems; reductions to parallel algorithms

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

Related Items

Unnamed Item, A one pass streaming algorithm for finding Euler tours

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple randomized parallel algorithm for list-ranking
• Selection and sorting with limited storage
• The space complexity of approximating the frequency moments
• List-ranking on interconnection networks.
• Data Stream Management
• High-Probability Parallel Transitive-Closure Algorithms
• Fast, small-space algorithms for approximate histogram maintenance
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• An O(logn) parallel connectivity algorithm
• An Approximate L¹ -Difference Algorithm for Massive Data Streams
• Communication Complexity
• Automata, Languages and Programming
• Trading off space for passes in graph streaming problems