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.68038OpenAlexW2081385108MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time ⋮ 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∗† ⋮ Parallel algorithms for arrangements ⋮ Parallel evaluation of arithmetic circuits ⋮ Efficient massively parallel implementation of some combinatorial algorithms ⋮ Exploiting few inversions when sorting: Sequential and parallel algorithms ⋮ o(log4 n) time parallel maximal matching algorithm using linear number of processors ⋮ A note on the 1-maximal elements problem ⋮ Efficient parallel graph algorithms for coarse grained multicomputers and BSP ⋮ An optimal parallel algorithm for the minimum circle-cover problem ⋮ Optimal parallel colouring algorithms for totally decomposable graphs ⋮ A time-optimal solution for the path cover problem on cographs. ⋮ Scalability and communication in parallel low-complexity lossless compression ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ Finding a minimal cover for binary images: An optimal parallel algorithm ⋮ TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION ⋮ A unified approach to parallel depth-first traversals of general trees ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses ⋮ Breadth-first traversal of trees and integer sorting in parallel ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ Randomized parallel list ranking for distributed memory multiprocessors. ⋮ 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 ⋮ Efficient parallel term matching and anti-unification ⋮ An optimal parallel algorithm for computing furthest neighbors in a tree ⋮ Optimal parallel algorithms on planar graphs ⋮ Deterministic parallel backtrack search ⋮ 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 ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ 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 ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases ⋮ Deterministic parallel list ranking ⋮ Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗
