Title

Random-Tree Diameter And The Diameter-Constrained Mst

Keywords

Constrained minimum spanning tree; Greedy algorithm; Tree diameter

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 n 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 ≤ k ≤ (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.

Publication Date

12-1-2002

Publication Title

International Journal of Computer Mathematics

Volume

79

Issue

6

Number of Pages

651-663

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/00207160211289

Socpus ID

28344431540 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/28344431540

This document is currently not available here.

Share

COinS