Random-tree diameter and the diameter-constrained MST

    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