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

A note on space spanning

โœ Scribed by Nelson H. F. Beebe

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
166 KB
Volume
6
Category
Article
ISSN
0020-7608

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A note on spanning with options
A note on spanning with options
โœ Valentina Galvani ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 159 KB
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 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.

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
โœ Fred Buckley; Martin Lewinter ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 182 KB ๐Ÿ‘ 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th