Computation of constrained spanning trees: A unified approach

    Authors

    N. Deo;N. Kumar

    Comments

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

    Keywords

    BOUND ALGORITHM; STEINER PROBLEM; GRAPH; FORMULATIONS; PERFORMANCE; COMPLEXITY; NETWORKS; DESIGN; FIND; Economics; Operations Research & Management Science; Mathematics, ; Applied; Mathematics, Interdisciplinary Applications; Social Sciences, ; Mathematical Methods

    Abstract

    Computing spanning trees with specific properties and constraints lies at the heart of many real-life network optimization problems. Here, a compilation of 29 constrained spanning tree problems is presented. Since most of these problems are NP-complete, good approximate heuristics are needed to solve them on parallel machines. We develop two generic methods for handling large graphs on massively-parallel SIMD machines. The first method is for problems in which the goal is to find a spanning tree which satisfies a specified constraint while minimizing its total weight. First, a minimum spanning tree (MST) of the given weighted graph is computed without considering the specified constraint. Then the constraint is used to increase the weights of selected edges (in this tree) in order that when the next MST is constructed (in the graph with modified edge weights) it has fewer violations of the constraint. Next, an MST of the graph with altered weights is computed. This iterative procedure of increasing the edge weights followed by the MST computation is repeated until a spanning tree without constraint violations is obtained. The second method, on the other hand, constructs a spanning tree once and for all - employing problem-specific heuristics in every step of the tree-construction. As case studies, we consider two sample problems (Degree-Constrained MST and Minimum-Length Fundamental-Cycle-Set) - one for each of the two methods. Our extensive empirical study on well-known benchmark problems as well as on randomly-generated graphs shows that the quality of solutions for both the problems is promising and the execution-times, reasonable for graphs with thousands of nodes and several million edges. Finally, to demonstrate the generality of our approach, we outline how to apply these two methods to three additional problems from the list, namely - Capacitated MST, Maximum-Leaf Spanning Tree, and Optimum-Communication Spanning Tree. For the Optimum-Communication Spanning Tree, a hybrid of the two methods is employed.

    Journal Title

    Network Optimization

    Volume

    450

    Publication Date

    1-1-1997

    Document Type

    Article

    Language

    English

    First Page

    194

    Last Page

    220

    WOS Identifier

    WOS:000071439800010

    ISSN

    0075-8442; 3-540-62541-0

    Share

    COinS