Expected Lengths of Minimum Spanning Trees for Non-identical Edge Distributions

Wenbo V. Li (University of Delaware)
Xinyi Zhang (FHCRC)

Abstract


An exact general formula for the expected length of the minimal spanning tree (MST) of a connected (possibly with loops and multiple edges) graph whose edges are assigned lengths according to independent (not necessarily identical) distributed random variables is developed in terms of the multivariate Tutte polynomial (alias Potts model). Our work was inspired by Steele's formula based on two-variable Tutte polynomial under the model of uniformly identically distributed edge lengths. Applications to wheel graphs and cylinder graphs are given under two types of edge distributions.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 110-141

Publication Date: February 3, 2010

DOI: 10.1214/EJP.v15-735

References

  1. Avram, Florin; Bertsimas, Dimitris. The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach. Ann. Appl. Probab. 2 (1992), no. 1, 113--130. MR1143395 (93b:60027)
  2. Beveridge, Andrew; Frieze, Alan; McDiarmid, Colin. Random minimum length spanning trees in regular graphs. Combinatorica 18 (1998), no. 3, 311--333. MR1721947 (2001c:05128)
  3. Frieze, A. M.; McDiarmid, C. J. H. On random minimum length spanning trees. Combinatorica 9 (1989), no. 4, 363--374. MR1054012 (91j:05092)
  4. Frieze, A. M. On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 (1985), no. 1, 47--56. MR0770868 (86d:05103)
  5. Frieze, Alan; Ruszinkó, Miklós; Thoma, Lubos. A note on random minimum length spanning trees. Electron. J. Combin. 7 (2000), Research Paper 4, 5 pp. (electronic). MR1774728 (2001d:05169)
  6. Gamarnik, David. The expected value of random minimal length spanning tree of a complete graph. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 700--704 (electronic), ACM, New York, 2005. MR2298322
  7. Horn, Roger A.; Johnson, Charles R. Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press, Cambridge, 1990. xiv+561 pp. ISBN: 0-521-38632-2 MR1084815 (91i:15001)
  8. Hutson, Kevin; Lewis, Thomas M. The expected length of a minimal spanning tree of a cylinder graph. Combin. Probab. Comput. 16 (2007), no. 1, 63--83. MR2286512 (2008c:05034)
  9. Janson, Svante. The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph. Random Structures Algorithms 7 (1995), no. 4, 337--355. MR1369071 (97d:05244)
  10. Kreweras, G. Sur les partitions non croisées d'un cycle. (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852)
  11. Li, Wenbo V.; Zhang, Xinyi. On the difference of expected lengths of minimum spanning trees. Combin. Probab. Comput. 18 (2009), no. 3, 423--434. MR2501434
  12. Penrose, Mathew D. Random minimal spanning tree and percolation on the $N$-cube. Random Structures Algorithms 12 (1998), no. 1, 63--82. MR1637395 (99g:60024)
  13. Sokal, Alan D. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. Surveys in combinatorics 2005, 173--226, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005. MR2187739 (2006k:05052)
  14. Smith, C. A. B.; Tutte, W. T. A class of self-dual maps. Canadian J. Math. 2, (1950). 179--196. MR0036496 (12,118f)
  15. Steele, J. Michael. On Frieze's $zeta(3)$ limit for lengths of minimal spanning trees. Discrete Appl. Math. 18 (1987), no. 1, 99--103. MR0905183 (88i:05063)
  16. Steele, J. Michael. Minimal spanning trees for graphs with random edge lengths. Mathematics and computer science, II (Versailles, 2002), 223--245, Trends Math., Birkhäuser, Basel, 2002. MR1940139 (2003i:60015)
  17. Tutte, W. T. Squaring the square. Canadian J. Math. 2, (1950). 197--209. MR0036497 (12,118g)
  18. Varga, Richard S. Matrix iterative analysis. Prentice-Hall, Inc., Englewood Cliffs, N.J. 1962 xiii+322 pp. MR0158502 (28 #1725)
  19. Zhang, Xinyi The Expected Lengths of Minimum Spanning Trees. PhD thesis, University of Delaware. (May 2008).
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.