✦ LIBER ✦

An 0(|E|loglog|V|) algorithm for finding minimum spanning trees

✍ Scribed by Andrew Chi-chih Yao

Book ID: 113161824
Publisher: Elsevier Science
Year: 1975
Tongue: English
Weight: 379 KB
Volume: 4
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(75)90056-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An Algorithm for Finding K Minimum Spann

An Algorithm for Finding K Minimum Spanning Trees

✍ Katoh, N.; Ibaraki, T.; Mine, H. 📂 Article 📅 1981 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 964 KB

Algorithms for finding and updating mini

Algorithms for finding and updating minimum-depth spanning trees in parallel

✍ Pranay Chaudhuri; Asad A. Ismaeel 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 564 KB

An adaptive and cost-optimal parallel al

An adaptive and cost-optimal parallel algorithm for minimum spanning trees

✍ S. G. Akl 📂 Article 📅 1986 🏛 Springer Vienna 🌐 English ⚖ 388 KB

Efficient algorithms for finding minimum

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

✍ Harold N. Gabow; Zvi Galil; Thomas Spencer; Robert E. Tarjan 📂 Article 📅 1986 🏛 Springer-Verlag 🌐 English ⚖ 939 KB

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 linear-time algorithm for finding a mi

A linear-time algorithm for finding a minimum spanning pseudoforest

✍ Harold N. Gabow; Robert E. Tarjan 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 460 KB