28-05-2014, 11:36 AM
MINIMUM WEIGHT SPANNING TREES WITH BOUNDED DIAMETER
ABSTRACT
Let G be a simple graph with non-negative edge weights. Determining
a minimum weight spanning tree is a fundamental problem that arises in
network design and as a subproblem in many combinatorial optimization
problems such as vehicle routing.
In some applications, it is
necessary to restrict the diameter of the spanning tree and thus one is
interested in the problem :
Find, in a given weighted graph G, a minimum weight
spanning tree of diameter at most D.
This problem is known to be NP-complete for D 2:: 4.
In this paper we
present a mixed integer linear programming formulation and discuss some
solution procedures.