Random-tree Diameter and the Diameter-constrained MST
Titel:
Random-tree Diameter and the Diameter-constrained MST
Auteur:
Abdalla, Ayman Deo, Narsingh
Verschenen in:
International journal of computer mathematics
Paginering:
Jaargang 79 (2002) nr. 6 pagina's 651-663
Jaar:
2002
Inhoud:
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.
Tijdschrift beschrijving