|
Published Articles >> Table of Contents >> Abstract
1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)
p. 184
A Parallel Algorithm for the Degree-Constrained Minimum Spanning Tree Problem Using Nearest-Neighbor Chains
Li-Jen Mao, University of Central Florida
Narsingh Deo, University of Central Florida
Sheau-Dong Lang, University of Central Florida
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778937
Send link to a friend
| 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 <= d <= (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. Our experimental results show that while the IR algorithm is faster, the TC-RNN algorithm consistently produces spanning trees with a smaller weight. In this paper, 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.
|
 Additional Information
|
Index Terms- Parallel approximate algorithm, degree-constrained MST, minimum spanning tree, reciprocal nearest neighbors
Citation:
Li-Jen Mao, Narsingh Deo, Sheau-Dong Lang,
"A Parallel Algorithm for the Degree-Constrained Minimum Spanning Tree Problem Using Nearest-Neighbor Chains,"
ispan,
p. 184,
1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99),
1999
|
|
