Bounded-diameter minimum spanning trees and related problems

Abstract

We consider the problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean plane. The diameter of a spanning tree is the maximum distance between any two points in the tree. We give a characterization of an MDST and present a θ(n3) time algorithm for solving the prohlem. We also show that for a weighted undirected graph, the problem of determining if a. spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is NP-complete. The geometrical minimum diameter Steiner tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in O(n) time.