✦ LIBER ✦

Minimum restricted diameter spanning trees

✍ Scribed by Refael Hassin; Asaf Levin

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 304 KB
Volume: 137
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00360-3

No coin nor oath required. For personal study only.

✦ Synopsis

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 with requirement between them. The minimum restricted diameter spanning tree problem is to ÿnd a spanning tree T such that the restricted diameter is minimized. We prove that the minimum restricted diameter spanning tree problem is NP-hard and that unless P = NP there is no polynomial time algorithm with performance guarantee of less than 2. In the case that G contains isolated vertices and the length matrix is deÿned by distances over a tree we prove that there exists a tree over the non-isolated vertices such that its restricted diameter is at most 4 times the minimum restricted diameter and that this constant is at least 3 1 2 . We use this last result to present an O(log(n))-approximation algorithm.

📜 SIMILAR VOLUMES

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

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

The minimum labeling spanning trees

✍ Ruay-Shiung Chang; Leu Shing-Jiuan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 449 KB

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

Network flow models for designing diamet

Network flow models for designing diameter-constrained minimum-spanning and Steiner trees

✍ Luis Gouveia; Thomas L. Magnanti 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

A 2-path approach for odd-diameter-const

A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees

✍ Luis Gouveia; Thomas L. Magnanti; Cristina Requejo 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

On Minimum Edge Ranking Spanning Trees

✍ Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 243 KB

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard.