Title

Parallel Algorithms For The Degree-Constrained Minimum Spanning Tree Problem Using Nearest-Neighbor Chains And The Heap-Traversal Technique

Keywords

degree-constrained minimum spanning tree; heap traversal; nearest neighbor chain; Parallel approximate algorithm

Abstract

The degree-constrained minimum spanning tree (d-MST) problem attempts to find a minimum spanning tree with an added constraint that no nodes in the tree have a degree larger than a specified integer d. It is known that 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 (heuristics) have been proposed in the literature. We have previously proposed three approximate algorithms, IR, TC-RNN, and TC-NNC, for solving the d-MST problem, the last two (TC-RNN and TC-NNC) take advantage of nearest neighbors and their properties. Our experimental results showed that both the TC-RNN and TC-NNC algorithms consistently produce spanning trees with a smaller weight (better quality-of-solution) than that of IR, but using slightly longer execution time. We propose a new heap traversal technique that further improves the time efficiency of TC-RNN and TC-NNC. Our experiments using randomly generated, weighted graphs as inputs show that the TC-NNC algorithm outperforms the other two approximate algorithms in terms of the execution time and quality-of-solution.

Publication Date

1-1-2002

Publication Title

Proceedings of the International Conference on Parallel Processing Workshops

Volume

2002-January

Number of Pages

398-404

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICPPW.2002.1039757

Socpus ID

63549148186 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS