✦ LIBER ✦

A note on spanning with options

✍ Scribed by Valentina Galvani

Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 159 KB
Volume: 54
Category: Article
ISSN: 0165-4896
DOI: 10.1016/j.mathsocsci.2007.03.002

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A note on space spanning

✍ Nelson H. F. Beebe 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB

Spanning, valuation and options

✍ Donald J. Brown; Stephen A. Ross 📂 Article 📅 1991 🏛 Springer 🌐 English ⚖ 717 KB

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

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.