𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improving the efficiency of parallel minimum spanning tree algorithms

✍ Scribed by Ka Wong Chong; Yijie Han; Yoshihide Igarashi; Tak Wah Lam

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
203 KB
Volume
126
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents results which improve the e ciency of parallel algorithms for computing the minimum spanning trees. For an input graph with n vertices and m edges our EREW PRAM algorithm runs in O(log n) time with O((m+n) log n) operations. Our CRCW PRAM algorithm runs in O(log n) time with O((m + n) log log n) operations. We also show that for dense graphs we can achieve O(log n) time with O(n 2 ) operations on the EREW PRAM.

πŸ“œ SIMILAR VOLUMES

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

Efficient distributed algorithm to solve
Efficient distributed algorithm to solve updating minimum spanning tree problem
✍ Jungho Park; Ken'Ichi Hagihara; Nobuki Tokura; Toshimitsu Masuzawa πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 983 KB

## Abstract This paper proposes a distributed algorithm for reconstructing a minimum‐weight spanning tree __T__β€² of a network __N__β€² when link addition and deletion occur in a network __N__ with a minimum‐weight spanning tree __T.__ In this algorithm each processor uses information whose adjacent l