Minimum-Weight Degree-Constrained Spanning Tree Problem: Heuristics And Implementation On An Simd Parallel Machine

    Authors

    B. Boldon; N. Deo;N. Kumar

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    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

    WOS:A1996UN31400002

    ISSN

    0167-8191

    Share

    COinS