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

Computational experience with minimum spanning tree algorithms

โœ Scribed by J.P. Jarvis; D.E. Whited

Book ID
107917067
Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
538 KB
Volume
2
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

๐Ÿ“œ 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

Offline Algorithms for Dynamic Minimum S
Offline Algorithms for Dynamic Minimum Spanning Tree Problems
โœ D. Eppstein ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 651 KB

We describe an efficient algorithm for maintaining a minimum spanning tree (MST) in a graph subject to a sequence of edge weight modifications. The sequence of minimum spanning trees is computed offline, after the sequence of modifications is known. The algorithm takes time \(O(k \log n)\) for a seq