The complexity of parallel prefix problems on small domains

DOI10.1006/inco.1997.2654zbMath0889.68068OpenAlexW2084408735MaRDI QIDQ1373137

Jaikumar Radhakrishnan, Shiva P. Chaudhuri

Publication date: 2 June 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5e26dfb91733a4dd8a422bee409246cd2f3bf6d7

zbMATH Keywords

CRCW-PRAM model

Mathematics Subject Classification ID

Searching and sorting (68P10) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded fan-in circuits and associative functions
• Simulations among concurrent-write PRAMs
• Improved deterministic parallel integer sorting
• Randomized range-maxima in nearly-constant parallel time
• Sensitive functions and approximate problems
• On Parallel Searching
• The Complexity of Parallel Sorting
• On parallel hashing and integer sorting
• Recursive Star-Tree Parallel Data Structure
• Tight Bounds on Oblivious Chaining
• The Parallel Simplicity of Compaction and Chaining
• Optimal bounds for decision problems on the CRCW PRAM
• The log-star revolution

This page was built for publication: The complexity of parallel prefix problems on small domains