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

A note on the minimum label spanning tree

โœ Scribed by Yingyu Wan; Guoliang Chen; Yinlong Xu

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
44 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n -1) + 1)-approximation for any graph with n nodes (n > 1), which improves the known performance guarantee 2 ln n + 1.

๐Ÿ“œ SIMILAR VOLUMES

The minimum labeling spanning trees
The minimum labeling spanning trees
โœ Ruay-Shiung Chang; Leu Shing-Jiuan ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 449 KB

One of the fundamental problems in graph theory is to compute a minimum weight spanning tree. In this paper, a variant of spanning trees, called the minimum labeling spanning tree, is studied. The purpose is to find a spanning tree that tries to use edges that are as similar as possible. Giving each

A note on bisecting minimum spanning tre
A note on bisecting minimum spanning trees
โœ W. M. Boyce; M. R. Garey; D. S. Johnson ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 281 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