Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time

DOI10.1137/0217009MaRDI QIDQ3777447zbMATH OpenOpenAlexFDO

Authors Uzi Vishkin, Richard 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

zbMATH Keywords

schedulinglist rankingexpander graphsPRAM algorithmapproximate reschedulingsoptimal speed-up

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• scientific article; zbMATH DE number 1760037
• Approximation algorithms for general parallel task scheduling
• A parallel approximation scheme for the multiprocessor scheduling problem
• Approximation schemes for scheduling on parallel machines
• Approximation algorithms for scheduling parallel jobs
• scientific article; zbMATH DE number 1444289
• Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
• scientific article; zbMATH DE number 1375583
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems

Cited in

(52)

• THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK
• Efficient parallel term matching and anti-unification
• Randomized parallel list ranking for distributed memory multiprocesors
• Deterministic parallel backtrack search
• A time-optimal solution for the path cover problem on cographs.
• Optimal parallel colouring algorithms for totally decomposable graphs
• An optimal parallel algorithm for the minimum circle-cover problem
• A unified approach to parallel depth-first traversals of general trees
• Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
• An optimal parallel algorithm for computing furthest neighbors in a tree
• Efficient parallel algorithms for shortest paths in planar digraphs
• More general parallel tree contraction: Register allocation and broadcasting in a tree
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
• THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†
• Parallel construction and query of index data structures for pattern matching on square matrices
• Optimal parallel algorithms on planar graphs
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• A note on the 1-maximal elements problem
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
• Optimal parallel algorithms on circular-arc graphs
• Optimal parallel algorithms for multiple updates of minimum spanning trees
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗
• TIME AND ENERGY OPTIMAL LIST RANKING ALGORITHMS ON THE k-CHANNEL BROADCAST COMMUNICATION MODEL WITH NO COLLISION DETECTION
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• A simple optimal parallel algorithm for the minimum coloring problem on interval graphs
• Efficient massively parallel implementation of some combinatorial algorithms
• scientific article; zbMATH DE number 1444289 (Why is no real title available?)
• A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
• Sorting in linear time?
• Exploiting few inversions when sorting: Sequential and parallel algorithms
• Finding a minimal cover for binary images: An optimal parallel algorithm
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Breadth-first traversal of trees and integer sorting in parallel
• Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
• An optimal parallel algorithm for node ranking of cographs
• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• scientific article; zbMATH DE number 4064467 (Why is no real title available?)
• Scalability and communication in parallel low-complexity lossless compression
• Efficient parallel graph algorithms for coarse grained multicomputers and BSP
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
• A nearly parallel algorithm for the Voronoi diagram of a convex polygon
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Parallel evaluation of arithmetic circuits
• Parallel algorithms for arrangements
• Deterministic parallel list ranking
• Data independence of read, write, and control structures in PRAM computations
• Randomized parallel list ranking for distributed memory multiprocessors.
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models

This page was built for publication: Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777447)