Approximation algorithms for the shortest total path length spanning tree problem (Q1582085)

Given an undirected graph with nonnegative weights on the edges, the shortest total path length spanning tree problem is to find a spanning tree minimizing the sum of distances between all pairs of different vertices. This problem is NP-complete. The present paper gives polynomial time approximation algorithms with different time bounds and worst case ratios. Meantime a polynomial time approximation scheme is known; see \textit{B. Y. Wu. G. Lancia, V. Bafna, K.-M. Chao}, and \textit{R. Ravi} [SIAM J. Comput. 29, No. 3, 761-778 (2000; Zbl 0941.68159)].