On the complexity of bicriteria spanning tree problems for a set of points in the plane

A spanning tree is a very simple and common communication network model. The minimum (cost) spanning tree (MST) of a connected graph G = (V, E) may not be unique if two or more edges have the same cost. The transmission delay between two nodes in a spanning tree network is measured in terms of its path length. When the minimum cost spanning tree is not unique, the one that minimizes transmission delay is desired. The bicriteria (total cost and transmission delay) optimization problem, the so called minimum radius minimum cost spanning tree or the minimum diameter minimum cost spanning tree problems is known to be NP-hard. Its geometrical version was open. In this dissertation, it is shown that for given point set in the plane, the problem of determining the existence of a spanning tree with total weight and radius (or diameter) upper-bounded, by two given parameters C and R (or D), respectively is NP-complete. An O(m log n) time algorithm is presented for computing the union graph and the intersection graph of all MST's, where m = |E| and n = |V|. Also presented are some heuristic algorithms for finding a suboptimal minimum radius (or diameter) minimum spanning tree. It is shown that the heuristic algorithm based on a locally optimal connection strategy can have an O(n1/3) performance ratio in some cases, where n is the number of points. Experimental results indicate that the heuristic based on a modified Prim's MST algorithm, MST_H1 outperforms Prim's MST (minimum spanning tree algorithm) overall and the output of the heuristic can be used as a new oracle MST for other problems. This may contribute to improving performance of many heuristic algorithms for other problems where an initial (arbitrary) MST is needed.