Deterministic parallel list ranking
From MaRDI portal
Publication:808699
DOI10.1007/BF01759076zbMath0732.68045MaRDI QIDQ808699
Richard J. Anderson, Gary Lee Miller
Publication date: 1991
Published in: Algorithmica (Search for Journal in Brave)
Related Items
Improved parallel depth-first search in undirected planar graphs, An optimal parallel algorithm for planar cycle separators, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗, Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM, Conservative algorithms for parallel and sequential integer sorting, A time-optimal solution for the path cover problem on cographs., List-ranking on interconnection networks., Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees, Data independence of read, write, and control structures in PRAM computations, An efficient parallel algorithm for building the separating tree, Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees, A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles, More Efficient Parallel Integer Sorting, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, More general parallel tree contraction: Register allocation and broadcasting in a tree, PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs
Cites Work
- Unnamed Item
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Faster optimal parallel prefix sums and list ranking
- An Efficient Parallel Biconnectivity Algorithm
- Deterministic coin tossing with applications to optimal parallel list ranking
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
