Research work · 2003
A parallel algorithm for the degree-constrained minimum spanning tree problem using nearest-neighbor chains
Li-Jen Mao, Narsingh Deo, Sheau-Dong Lang
International Symposium on Pervasive Systems, Algorithms and Networks (ISPAN)
Abstract
The Minimum Spanning Tree (MST) problem with an added constraint that no node in the spanning tree has the degree more than a specified integer d, is known as the Degree-Constrained MST (d-MST) problem. Since computing the d-MST is NP-hard for every d in the range 2/spl les/d/spl les/(n-2) where n denotes the total number of nodes, several approximate algorithms have been proposed in the literature. We have previously proposed two approximate algorithms, TC-RNN and IR, for the d-MST problem (L.J. Mao et al., 1997). Our experimental results show that while the IR algorithm is faster, the TC-RNN algorithm consistently produces spanning trees with a smaller weight. We propose a new algorithm, TC-NNC, which is an improved version of TC-RNN. Our experiments using randomly generated, weighted graphs as input, demonstrate that the execution time of TC-NNC is smaller than that of TC-RNN, and is very close to that of IR. Further, the quality-of-solution of TC-NNC is better than that of IR and is very close to that of TC-RNN.