Minimum spanning trees on random networks

Citation
R. Dobrin et Pm. Duxbury, Minimum spanning trees on random networks, PHYS REV L, 86(22), 2001, pp. 5076-5079
Citations number
26
Categorie Soggetti
Physics
Journal title
PHYSICAL REVIEW LETTERS
ISSN journal
00319007 → ACNP
Volume
86
Issue
22
Year of publication
2001
Pages
5076 - 5079
Database
ISI
SICI code
0031-9007(20010528)86:22<5076:MSTORN>2.0.ZU;2-1
Abstract
We show that the geometry of minimum spanning trees (MST) on random graphs is universal. Because of this geometric universality, we are able to charac terize the energy of MST using a scaling distribution [P(epsilon)] found us ing uniform disorder. We show that the MST energy for other disorder distri butions is simply related to P(epsilon). We discuss the relationship to inv asion percolation, to the directed polymer in a random media, to uniform sp anning trees, and also the implications for the broader issue of universali ty in disordered systems.