๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A simple randomized parallel algorithm for list-ranking

โœ Scribed by Richard J. Anderson; Gary L. Miller

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
506 KB
Volume
33
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Randomized Parallel Algorithm for Plan
A Randomized Parallel Algorithm for Planar Graph Isomorphism
โœ Hillel Gazit; John H Reif ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph ลฝ ลฝ 2 . 1 q โ‘€ which can be computed by known algorithms in O log n time with

A Randomized Parallel Algorithm for Sing
A Randomized Parallel Algorithm for Single-Source Shortest Paths
โœ Philip N Klein; Sairam Subramanian ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 179 KB

We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is ba

A Simple Optimal Parallel Algorithm for
A Simple Optimal Parallel Algorithm for a Core of a Tree
โœ S.T. Peng; W.T. Lo ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 354 KB

A core of a tree \(T=(V, E)\) is a path in \(T\) which minimizes \(\Sigma_{v \in V}\) \(d(v, P)\), where \(d(v, P)\), the distance from a vertex \(v\) to path \(P\), is defined as \(\min _{u \in P} d(v, u)\). We present an optimal parallel algorithm to find a core of \(T\) in \(O(\log n)\) time usin