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

On the value of a random minimum spanning tree problem

โœ Scribed by A.M. Frieze

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
324 KB
Volume
10
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On finding a minimum spanning tree in a
On finding a minimum spanning tree in a network with random weights
โœ Colin McDiarmid; Theodore Johnson; Harold S. Stone ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 221 KB ๐Ÿ‘ 2 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e ลฝ . have independent identically distributed random weights w e . We find that when the kth ' ลฝ . edge e is added to the current tree

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.