Computational methods for the diameter restricted minimum weight spanning tree problem.

Abstract

Let G be a simple undirected graph with non-negative edge weights. In this paper we consider the following combinatorial optimization problem: Find, in G, a minimum weight spanning tree having diameter at most D. This problem is trivial for D:S 3 and NP-complete for D:: 4. In this paper we develop and implement a number of Branch and Bound algorithms for this problem. Computational results, based on simulated problems, are discussed. 1.