Adapting parallel algorithms to the W-stream model, with applications to graph problems
From MaRDI portal
Publication:410728
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
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
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 L1 -Difference Algorithm for Massive Data Streams
- Communication Complexity
- Automata, Languages and Programming
- Trading off space for passes in graph streaming problems