✦ LIBER ✦

A simpler minimum spanning tree verification algorithm

✍ Scribed by V. King

Book ID: 110548555
Publisher: Springer
Year: 1997
Tongue: English
Weight: 450 KB
Volume: 18
Category: Article
ISSN: 0178-4617
DOI: 10.1007/bf02526037

No coin nor oath required. For personal study only.

📜 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

A probabilistic minimum spanning tree al

A probabilistic minimum spanning tree algorithm

✍ F. James Rohlf 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 776 KB

Distributed verification of minimum span

Distributed verification of minimum spanning trees

✍ Amos Korman; Shay Kutten 📂 Article 📅 2007 🏛 Springer-Verlag 🌐 English ⚖ 328 KB

A fast algorithm for the minimum spannin

A fast algorithm for the minimum spanning tree

✍ Francis Suraweera 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 408 KB

A parallel algorithm for constructing mi

A parallel algorithm for constructing minimum spanning trees

✍ Jon Louis Bentley 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 521 KB

A Parallel Algorithm for Computing Minim

A Parallel Algorithm for Computing Minimum Spanning Trees

✍ D.B. Johnson; P. Metaxas 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 840 KB

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph \(G=(V, E)\) of \(n=|V|\) vertices and \(m=|E|\) edges on an EREW PRAM in \(O\left(\log ^{3 / 2} n\right)\) time using \(n+m\) processors. This represents a substantial improvement i