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

An optimal EREW PRAM algorithm for minimum spanning tree verification

โœ Scribed by Valerie King; Chung Keung Poon; Vijaya Ramachandran; Santanu Sinha

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
661 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(logn) time and O(m + n) work. The algorithm is a parallelization of King's linear time sequential algorithm for the problem. @

๐Ÿ“œ SIMILAR VOLUMES

Optimal Randomized EREW PRAM Algorithms
Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
โœ Shay Halperin; Uri Zwick ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 384 KB

We present the first randomized O log n time and O m + n work EREW PRAM algorithm for finding a spanning forest of an undirected graph G = V E with n vertices and m edges. Our algorithm is optimal with respect to time, work, and space. As a consequence we get optimal randomized EREW PRAM algorithms

An optimal EREW parallel algorithm for c
An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
โœ H.S. Chao; F.R. Hsu; R.C.T. Lee ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 498 KB

Given a undirected graph G, the breadth-first search tree is constructed by a breadth-first search on G. In this paper, an optimal parallel algorithm is presented for constructing the breadth-first search tree for permutation graphs in O(log n) time by using O(n/Iog n) processors under the EREW PRAM