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

A Note on the Shortest Spanning Tree Problem, by

โœ Scribed by James R. Evans

Book ID
109147548
Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
205 KB
Volume
10
Category
Article
ISSN
0016-7363

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
โœ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 150 KB ๐Ÿ‘ 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami

A note on a spanning 3-tree
A note on a spanning 3-tree
โœ Masao Tsugaki ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 316 KB
A note on the minimum label spanning tre
A note on the minimum label spanning tree
โœ Yingyu Wan; Guoliang Chen; Yinlong Xu ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 44 KB

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.