Finding bounded diameter minimum spanning tree in general graphs

Given a connected, weighted, undirected graph G=(V,E) and a constant D≥2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight with diameter no more than D. A new algorithm addresses graphs with non-negative weights and has proven performance ratio of O1−Ddmin(|V|−1)w+/w−+1, where w+ (resp. w−) denotes the maximum (resp. minimum) edge weight in the graph, and dmin is the hop diameter of G. The running time of the algorithm is O|V|logD after minimum spanning tree of G is computed. The performance of the algorithm has been evaluated empirically as well.