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

The minimum labeling spanning trees

โœ Scribed by Ruay-Shiung Chang; Leu Shing-Jiuan

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
449 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

One of the fundamental problems in graph theory is to compute a minimum weight spanning tree. In this paper, a variant of spanning trees, called the minimum labeling spanning tree, is studied. The purpose is to find a spanning tree that tries to use edges that are as similar as possible. Giving each edge a label, the minimum labeling spanning tree is to find a spanning tree whose edge set consists of the smallest possible number of labels. This problem is shown to be NP-complete even for complete graphs. 'lXvo heuristic algorithms and an exact algorithm, based on the A*-algorithm, are presented. According to the experimental results, one of the heuristic algorithms is very effective and the exact algorithm is very efficient. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

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.

Worst-case behavior of the MVCA heuristi
Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
โœ Yupei Xiong; Bruce Golden; Edward Wasil ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 185 KB

In this paper, we review recent work on the minimum labeling spanning tree problem and obtain a new worst-case ratio for the MVCA heuristic. We also present a family of graphs in which the worst-case ratio can be attained. This implies that the new ratio cannot be improved any further.

Counting Minimum Weight Spanning Trees
Counting Minimum Weight Spanning Trees
โœ Andrei Z. Broder; Ernst W. Mayr ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 152 KB

We present an algorithm for counting the number of minimum weight spanning trees, based on the fact that the generating function for the number of spanning trees of a given graph, by weight, can be expressed as a simple determinant. For a graph with n vertices and m edges, our ลฝ ลฝ .. ลฝ . algorithm r

Minimum restricted diameter spanning tre
Minimum restricted diameter spanning trees
โœ Refael Hassin; Asaf Levin ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 304 KB

Let G = (V; E) be a requirement graph. Let d = (dij) n i; j=1 be a length metric. For a tree T denote by dT (i; j) the distance between i and j in T (the length according to d of the unique i -j path in T ). The restricted diameter of T , DT , is the maximum distance in T between pair of vertices wi

The Capacitated Minimum Spanning Tree
The Capacitated Minimum Spanning Tree
โœ K. M. Chandy; Tachen Lo ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 386 KB

## Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorith