An Empirical Study of Parallel Tree-Construction Algorithms for the Degree-Constrained Minimum Spanning Tree Problem

摘要

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 three approximate algorithms (heuristics), TC-RNN, TC-NNC and IR, for the d-MST problem. Our experimental results showed that while the IR algorithm was the fastest, the TC-RNN algorithm consistently produced spanning trees with a smaller weight (better quality-of-solution) than that of IR; the TC-NNC algorithm produced spanning trees of the quality of solutions similar to that of TC-RNN but of a slightly longer execution time than that of IR. In this paper, we propose a heap traversal technique and its application to the implementation of TC-NNC. The complexity analysis demonstrates that using the heap traversal technique may further improve the time efficiency of TC-NNC.