Computation of constrained spanning trees: A unified approach

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