𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computing capacitated minimal spanning trees efficiently

✍ Scribed by A. Kershenbaum

Publisher
John Wiley and Sons
Year
1974
Tongue
English
Weight
645 KB
Volume
4
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Minimal ratio spanning trees
Minimal ratio spanning trees
✍ R. Chandrasekaran πŸ“‚ Article πŸ“… 1977 πŸ› John Wiley and Sons 🌐 English βš– 323 KB
The Capacitated Minimum Spanning Tree
The Capacitated Minimum Spanning Tree
✍ K. M. Chandy; Tachen Lo πŸ“‚ Article πŸ“… 1973 πŸ› John Wiley and Sons 🌐 English βš– 386 KB

## Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorith

Uniform and minimal essential spanning f
Uniform and minimal essential spanning forests on trees
✍ Olle HΓ€ggstrΓΆm πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 252 KB

Uniform and minimal random spanning trees for finite graphs are well-known objects. Analogues of these for the nearest-neighbor graph on Z d have been studied by Pemantle and Alexander. Here we propose analogous definitions of uniform resp. minimal essential spanning forests for an infinite tree ⌫,

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