Faster optimal parallel prefix sums and list ranking

DOI10.1016/0890-5401(89)90036-9zbMath0684.68048OpenAlexW4213327355MaRDI QIDQ1825647

Uzi Vishkin, Richard John Cole

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90036-9

zbMATH Keywords

parallel algorithmPRAMprefix sumsparallel random access machineparallel list rankingCRCWmodel of parallel computationconcurrent-read concurrent-write

Mathematics Subject Classification ID

Related Items (42)

Finding level-ancestors in trees ⋮ An optimal parallel algorithm for sorting multisets ⋮ The parallel complexity of integer prefix summation ⋮ Parallel maximum independent set in convex bipartite graphs ⋮ Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ On the parallel computation of the biconnected and strongly connected co-components of graphs ⋮ An optimal parallel algorithm to construct a deap ⋮ An optimal parallel algorithm for planar cycle separators ⋮ The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time ⋮ An optimally efficient selection algorithm ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Fast and optimal simulations between CRCW PRAMs ⋮ A generalized parallel prefix sums algorithm for arbitrary size arrays ⋮ An Improved Parallel Prefix Sums Algorithm ⋮ A sublogarithmic convex hull algorithm ⋮ Parallel algorithms for Burrows-Wheeler compression and decompression ⋮ A class of almost-optimal size-independent parallel prefix circuits ⋮ Finding a minimal cover for binary images: An optimal parallel algorithm ⋮ Improved deterministic parallel integer sorting ⋮ Optimal parallel 3-coloring algorithm for rooted trees and its applications ⋮ An optimal parallel algorithm for the Euclidean distance maps of 2-D binary images ⋮ Fast prefix adders for non-uniform input arrival times ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees ⋮ On a compaction theorem of Ragde ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Parallel search algorithms for graphs and trees ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Optimal parallel algorithms on planar graphs ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Modular exponentiation via the explicit Chinese remainder theorem ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ Parallel prefix computation on extended multi-mesh network. ⋮ On parallel integer sorting ⋮ Deterministic parallel list ranking ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs ⋮ Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space ⋮ ON THE POWER OF SOME PRAM MODELS

Cites Work

• Unnamed Item
• On efficient parallel strong orientation
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Simulation of Parallel Random Access Machines by Circuits
• An Efficient Parallel Biconnectivity Algorithm
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Prefix Computation

This page was built for publication: Faster optimal parallel prefix sums and list ranking