Minimum routing cost spanning tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the minimum routing cost spanning tree of a <a href="/facts/Weighted_graph/W0MqKkyE">weighted graph</a> is a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> minimizing the sum of pairwise distances between vertices in the tree. It is also called the optimum distance spanning tree, shortest total path length spanning tree, minimum total distance spanning tree, or minimum average distance spanning tree. In an unweighted graph, this is the spanning tree of minimum <a href="/facts/Wiener_index/ablp743I">Wiener index</a>.
Hu (1974) writes that the problem of constructing these trees was proposed by Francesco Maffioli.
It is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a> to construct it, even for unweighted graphs. However, it has a <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">polynomial-time approximation scheme</a>. The approximation works by choosing a number 
 
 
 
 k
 
 
 {\displaystyle k}
 
 that depends on the approximation ratio but not on the number of vertices of the input graph, and by searching among all trees with 
 
 
 
 k
 
 
 {\displaystyle k}
 
 internal nodes.
The minimum routing cost spanning tree of an unweighted <a href="/facts/Interval_graph/oLwYI3uT">interval graph</a> can be constructed in linear time. A polynomial time algorithm is also known for <a href="/facts/Distance-hereditary_graph/T17SFUmL">distance-hereditary graphs</a>, weighted so that the weighted distances are hereditary.

Minimum routing cost spanning tree open-in-new

Minimum routing cost spanning tree