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

DOI10.1016/j.tcs.2010.08.030zbMath1234.68458OpenAlexW2017148867MaRDI 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 modelgraph problemsreductions to parallel algorithms

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (2)

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

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

This page was built for publication: Adapting parallel algorithms to the W-stream model, with applications to graph problems