Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
From MaRDI portal
Publication:3777447
DOI10.1137/0217009zbMath0637.68038MaRDI QIDQ3777447
Uzi Vishkin, Richard John Cole
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217009
scheduling; list ranking; expander graphs; PRAM algorithm; approximate reschedulings; optimal speed-up
68Q25: Analysis of algorithms and problem complexity
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
A note on the 1-maximal elements problem, Optimal parallel colouring algorithms for totally decomposable graphs, Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗, THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, o(log4 n) time parallel maximal matching algorithm using linear number of processors, TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION, Deterministic parallel backtrack search, Optimal parallel algorithms on planar graphs, Scalability and communication in parallel low-complexity lossless compression, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Randomized parallel list ranking for distributed memory multiprocessors., Efficient parallel term matching and anti-unification, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, Deterministic parallel list ranking, The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time, An optimal parallel algorithm for the minimum circle-cover problem, Finding a minimal cover for binary images: An optimal parallel algorithm, A unified approach to parallel depth-first traversals of general trees, Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses, Breadth-first traversal of trees and integer sorting in parallel, An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model, Efficient parallel algorithms for shortest paths in planar digraphs, An optimal parallel algorithm for computing furthest neighbors in a tree, Optimal parallel algorithms on circular-arc graphs, A nearly parallel algorithm for the Voronoi diagram of a convex polygon, An optimal parallel algorithm for node ranking of cographs, Sorting in linear time?, More general parallel tree contraction: Register allocation and broadcasting in a tree, Parallel construction and query of index data structures for pattern matching on square matrices, A simple optimal parallel algorithm for the minimum coloring problem on interval graphs, Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Parallel evaluation of arithmetic circuits, Efficient massively parallel implementation of some combinatorial algorithms, Exploiting few inversions when sorting: Sequential and parallel algorithms, A time-optimal solution for the path cover problem on cographs., Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, Parallel algorithms for arrangements, Optimal computation of shortest paths on doubly convex bipartite graphs, Data independence of read, write, and control structures in PRAM computations, Optimal parallel algorithms for multiple updates of minimum spanning trees
