Title

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

Keywords

Constrained problems; Heuristics; Minimum spanning tree; NP-complete; SIMD machines

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 tree (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.

Publication Date

1-1-1996

Publication Title

Parallel Computing

Volume

22

Issue

3

Number of Pages

369-382

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0167-8191(95)00010-0

Socpus ID

0030103806 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS