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

A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees

โœ Scribed by James Roskind and Robert E. Tarjan

Book ID
121484542
Publisher
INFORMS
Year
1985
Tongue
English
Weight
369 KB
Volume
10
Category
Article
ISSN
0364-765X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Property on Edge-disjoint Spanning Tre
A Property on Edge-disjoint Spanning Trees
โœ Hong-Jian Lai; Hongyuan Lai; Charles Payan ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 214 KB

Let G be a simple graph with n vertices and let G c denote the complement of G . Let ( G ) denote the number of components of G and G ( E ) the spanning subgraph of G with edge set E . where the minimum is taken over all such partitions . In [ Europ . J . Combin . 7 (1986) , 263 -270] , Payan conj

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
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.