Title
Minimum-Weight Degree-Constrained Spanning Tree Problem: Heuristics And Implementation On An Simd Parallel Machine
Abbreviated Journal Title
Parallel Comput.
Keywords
minimum spanning tree; constrained problems; NP-complete; SIMD machines; heuristics; TRAVELING SALESMAN PROBLEM; ALGORITHMS; SET; Computer Science, Theory & Methods
Abstract
The minimum spanning tree 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 minimum-weight degree-constrained spanning free (d-MST) problem. Such a constraint arises, for example, in VLSI routing trees, in backplane wiring, or in minimizing single-point failures for communication networks. The d-MST problem is NP-complete. Here, we develop four heuristics for approximate solutions to the problem and implement them on a massively-parallel SIMD machine, MasPar MP-1. An extensive empirical study shows that for random graphs on up to 5000 nodes (about 12.5 million edges), the heuristics produce solutions close to the optimal in less than 10 seconds. The heuristics were also tested on a number of TSP benchmark problems to compute spanning trees with a degree bound d = 3.
Journal Title
Parallel Computing
Volume
22
Issue/Number
3
Publication Date
1-1-1996
Document Type
Article
Language
English
First Page
369
Last Page
382
WOS Identifier
ISSN
0167-8191
Recommended Citation
"Minimum-Weight Degree-Constrained Spanning Tree Problem: Heuristics And Implementation On An Simd Parallel Machine" (1996). Faculty Bibliography 1990s. 1551.
https://stars.library.ucf.edu/facultybib1990/1551
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu