✦ LIBER ✦

On minimum spanning trees and the intergradation of clusters

✍ Scribed by Warshauer, Steven M. ;Smosna, Richard

Publisher: Springer
Year: 1981
Tongue: English
Weight: 588 KB
Volume: 13
Category: Article
ISSN: 0020-5958
DOI: 10.1007/bf01029800

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Maximizing the minimum voter satisfactio

Maximizing the minimum voter satisfaction on spanning trees

✍ Andreas Darmann; Christian Klamler; Ulrich Pferschy 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 689 KB

This paper analyzes the computational complexity involved in solving fairness issues on graphs, e.g., in the installation of networks such as water networks or oil pipelines. Based on individual rankings of the edges of a graph, we will show under which conditions solutions, i.e., spanning trees, ca

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

On the minimum diameter spanning tree pr

On the minimum diameter spanning tree problem

✍ Refael Hassin; Arie Tamir 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 199 KB

On the generalized minimum spanning tree

On the generalized minimum spanning tree problem

✍ Young-Soo Myung; Chang-Ho Lee; Dong-Wan Tcha 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 748 KB

Minimum Spanning Trees and Types of Diss

Minimum Spanning Trees and Types of Dissimilarities

✍ Bruno Leclerc 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 295 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.