Deterministic parallel list ranking
Lecture notes in computer sciencePublished 3 August 2006
Richard Anderson, Gary L. Miller
Citations120
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on EREW P-RAM with n/log n processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors.
Keywords
Computer Science
SIAM Journal on ComputingAn Efficient Parallel Biconnectivity Algorithm
523 Citations1985Robert E. Tarjan, Uzi Vishkin
A new algorithm for finding the blocks (biconnected components) of an undirected graph and a general algorithmic technique that simplifies and improves computation of various functions on trees is introduced.
Information and ControlDeterministic coin tossing with applications to optimal parallel list ranking
424 Citations1986Richard Cole, Uzi Vishkin
The algorithms apply a novel “random-like” deterministic technique that provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.
Parallel tree contraction and its application
409 Citations1985Gary L. Miller, John H. Reif
A bottom-up algorithm to handle trees which has two major advantages over the top-down approach: the control structure is straight forward and easier to implement facilitating new algorithms using fewer processors and less time; and problems for which it was too difficult or too complicated to find polylog parallel algorithms are now easy.
eCommons (Cornell University)The Complexity of Parallel Computations
200 Citations1979James Wyllie
This thesis describes an algorithm for the off-line MIN that organizes its computation in the form of a complete binary tree that relies on redundancy in its representation of the input graph, and introduces three techniques that permit the design of parallel algorithms that are efficient in terms of both their time and processor requirements.
SIAM Journal on ComputingApproximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
186 Citations1988Richard Cole, Uzi Vishkin
This work defines a novel scheduling problem, which leads to the first optimal logarithmic time PRAM algorithm for list ranking, and shows how to apply these results to obtain improved PRAM upper bounds for a variety of problems on graphs.
Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms
182 Citations1986Richard Cole, Uzi Vishkin
A new deterministic coin tossing technique that provides for a fast and eff ient b reak ing of a symmetr ic s i tuat ion in paral le l is introduced.
Approximate and exact parallel scheduling with applications to list, tree and graph problems
176 Citations1986Richard Cole, Uzi Vishkin
A novel scheduling problem is defined; it is solved by repeated, rapid, approximate reschedulings, which leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time.
SIAM Journal on ComputingOptimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
174 Citations1989Sanguthevar Rajasekaran, John H. Reif
The main result is an optimal randomized parallel algorithm for INTEGER_SORT, the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size.
Information and ComputationFaster optimal parallel prefix sums and list ranking
163 Citations1989Richard Cole, Uzi Vishkin
A parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) time using n/lognprocessors (optimal speedup) is presented.
Parallel symmetry-breaking in sparse graphs
156 Citations1987Andrew V. Goldberg, Serge Plotkin +1 more
Efficient deterministic techniques for breaking symmetry in parallel are described and applied to construct fast linear processor algorithms for several problems, including (&Dgr; + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees inPlanar graphs.
An optimal parallel algorithm for integer sorting
124 Citations1985John H. Reif
This work gives a new parallel algorithm for integer sorting where the integer keys are restricted to at most polynomial magnitude and is the first known where the product of the time and processor bounds are bounded by a linear function of the input size.
AlgorithmicaThe accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
112 Citations1988Richard Cole, Uzi Vishkin
A new general parallel algorithmic technique for computations on trees is presented, which provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation.
Optimal Tree Contraction in the EREW Model
71 Citations1988Hillel Gazit, Gary L. Miller +1 more
A deterministic parallel algorithm for parallel tree contraction that is optimal in the sense that the product P · T is equal to the input size and gives an O(log n) time algorithm when P = n/log n.
Randomized speed-ups in parallel computation
68 Citations1984Uzi Vishkin
Three randomized parallel algorithms are presented for the problem: one of these algorithms runs almost-surely in time of O(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.
POWER OF PARALLEL PREFIX.
42 Citations1985Clyde P. Kruskal, Larry Rudolph +1 more
Proceedings of the International Conference on Parallel ProcessingParallel Algorithms for Bucket Sorting and the Data Dependent Prefix Problem.
35 Citations1986Yijie Han, Robert A. Wagner
A parallel algorithm for the data dependent prefix problem is presented and a bucket sorting algorithm is developed to be used as a component of the prefix algorithm.
Designing fast and efficient parallel algorithms
13 Citations1987Yu Han
This dissertation presents parallel algorithms for some fundamental computational problems and presents a parallel algorithm for computing connected components for an undirected graph of e edges and n nodes in time.