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/0217009zbMATH Open0637.68038OpenAlexW2081385108MaRDI QIDQ3777447FDOQ3777447
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
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
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Cited In (52)
- Randomized parallel list ranking for distributed memory multiprocesors
- Efficient parallel term matching and anti-unification
- Deterministic parallel backtrack search
- Optimal parallel colouring algorithms for totally decomposable graphs
- A time-optimal solution for the path cover problem on cographs.
- An optimal parallel algorithm for the minimum circle-cover problem
- An optimal parallel algorithm for computing furthest neighbors in a tree
- A unified approach to parallel depth-first traversals of general trees
- Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
- Efficient parallel algorithms for shortest paths in planar digraphs
- More general parallel tree contraction: Register allocation and broadcasting in a tree
- AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
- THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- 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
- StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Optimal parallel algorithms for multiple updates of minimum spanning trees
- Optimal parallel algorithms on circular-arc graphs
- A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗
- Solving the shortest-paths problem on bipartite permutation graphs efficiently
- 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
- Title not available (Why is that?)
- 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
- Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗
- Title not available (Why is that?)
- Efficient parallel graph algorithms for coarse grained multicomputers and BSP
- An optimal parallel algorithm for node ranking of cographs
- o(log4 n) time parallel maximal matching algorithm using linear number of processors
- Scalability and communication in parallel low-complexity lossless compression
- 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
- Data independence of read, write, and control structures in PRAM computations
- Deterministic parallel list ranking
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK
- Randomized parallel list ranking for distributed memory multiprocessors.
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)
