Title

Random-tree diameter and the diameter-constrained MST

Authors

Authors

A. Abdalla;N. Deo

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Int. J. Comput. Math.

Keywords

tree diameter; greedy algorithm; constrained minimum spanning tree; Mathematics, Applied

Abstract

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G, with it nodes and a positive integer, k, find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k; 4 less than or equal to k less than or equal to (n-2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.

Journal Title

International Journal of Computer Mathematics

Volume

79

Issue/Number

6

Publication Date

1-1-2002

Document Type

Article

Language

English

First Page

651

Last Page

663

WOS Identifier

WOS:000176035700001

ISSN

0020-7160

Share

COinS