Minimum routing cost spanning tree

In computer science, the minimum routing cost spanning tree of a weighted graph is a spanning tree 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 Wiener index.[1] Hu (1974) writes that the problem of constructing these trees was proposed by Francesco Maffioli.[2]

It is NP-hard to construct it, even for unweighted graphs.[3][4] However, it has a polynomial-time approximation scheme. The approximation works by choosing a number ${\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 ${\displaystyle k}$ internal nodes.[5]

The minimum routing cost spanning tree of an unweighted interval graph can be constructed in linear time.[6] A polynomial time algorithm is also known for distance-hereditary graphs, weighted so that the weighted distances are hereditary.[7]

Fairness considerations

Several works assume that different people may have different preferences on edges in the graph, and the goal is to find a spanning tree that is "socially" best.

• Darmann, Klamler and Pferschy present a greedy algorithm that finds such a spanning tree.[8]

• Escoffier, Gourvès and Monnot study the problem under the egalitarian rule - maximizing the smallest utility of an agent.[9]
• Galand, Perny and Spanjaard study the problem under the criterion of minimizing the Choquet integral.[10]

See also

• Optimal network design - the problem of finding a spanning set (not necessarily a tree) that minimizes the sum of shortest path lengths.

References

1. Dobrynin, Andrey A.; Entringer, Roger; Gutman, Ivan (2001). "Wiener index of trees: theory and applications". Acta Applicandae Mathematicae. 66 (3): 211–249. doi:10.1023/A:1010767517079.
2. Hu, T. C. (September 1974). "Optimum Communication Spanning Trees". SIAM Journal on Computing. 3 (3): 188–195. doi:10.1137/0203015. MR 0427116.
3. Johnson, D. S.; Lenstra, J. K.; Kan, A. H. G. Rinnooy (December 1978). "The complexity of the network design problem" (PDF). Networks. 8 (4): 279–285. doi:10.1002/net.3230080402.
4. Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman. A2.1: ND3, p. 206. ISBN 978-0-7167-1044-8.
5. Wu, Bang Ye; Lancia, Giuseppe; Bafna, Vineet; Chao, Kun-Mao; Ravi, R.; Tang, Chuan Yi (January 2000). "A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees" (PDF). SIAM Journal on Computing. 29 (3): 761–778. doi:10.1137/S009753979732253X. S2CID 1639329.
6. Dahlhaus, Elias; Dankelmann, Peter; Ravi, R. (2004). "A linear-time algorithm to compute a MAD tree of an interval graph". Information Processing Letters. 89 (5): 255–259. doi:10.1016/j.ipl.2003.11.009. MR 2032568.
7. Dahlhaus, E.; Dankelmann, P.; Goddard, W.; Swart, H.C. (September 2003). "MAD trees and distance-hereditary graphs". Discrete Applied Mathematics. 131 (1): 151–167. doi:10.1016/S0166-218X(02)00422-5.
8. Darmann, Andreas; Klamler, Christian; Pferschy, Ulrich (April 2011). "Finding socially best spanning trees". Theory and Decision. 70 (4): 511–527. doi:10.1007/s11238-010-9228-1.
9. Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (March 2013). "Fair solutions for some multiagent optimization problems". Autonomous Agents and Multi-Agent Systems. 26 (2): 184–201. doi:10.1007/s10458-011-9188-z.
10. Galand, Lucie; Perny, Patrice; Spanjaard, Olivier (July 2010). "Choquet-based optimisation in multiobjective shortest path and spanning tree problems" (PDF). European Journal of Operational Research. 204 (2): 303–315. doi:10.1016/j.ejor.2009.10.015.