The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

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.