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 O((1 - D/d(min)(vertical bar V vertical bar-1)omega(+)/omega(-) + 1), omega(+) (resp. omega(-)) denotes the maximum (resp. minimum) edge weight in the graph, and d(min )is the hop diameter of G. The running time of the algorithm is O (vertical bar V vertical bar log D) after minimum spanning tree of G is computed. The performance of the algorithm has been evaluated empirically as well.

Automated summary

The bounded-diameter minimum spanning tree problem seeks to find a minimum weight spanning tree on a connected, weighted, undirected graph G with a diameter no more than D. A new algorithm has been developed that can handle graphs with non-negative weights and has been proven to have a certain performance ratio. The algorithm's performance has been evaluated empirically as well.