✦ LIBER ✦

Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests

✍ Scribed by Shay Halperin; Uri Zwick

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 384 KB
Volume: 39
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1146

No coin nor oath required. For personal study only.

✦ Synopsis

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 for other basic connectivity problems such as finding a bipartite partition, finding bridges and biconnected components, finding Euler tours in Eulerian graphs, finding an ear decomposition, finding an open ear decomposition, finding a strong orientation, and finding an st-numbering.

📜 SIMILAR VOLUMES

An optimal EREW PRAM algorithm for minim

An optimal EREW PRAM algorithm for minimum spanning tree verification

✍ Valerie King; Chung Keung Poon; Vijaya Ramachandran; Santanu Sinha 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 661 KB

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 proble