Models of Random Spanning Trees
Random Structures & Algorithms · 2026-05 · 68 (3)
DOI: 10.1002/rsa.70063 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 24.04.2026. Verfasst von Eric Babson und 5 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: National Science Foundation, Simons Laufer Mathematical Sciences Institute, University of California Berkeley.
Abstract (Originalsprache)
There are numerous randomized algorithms to generate spanning trees in a given ambient graph; several target the uniform distribution on trees (UST), while in practice the fastest and most frequently used draw random weights on the edges and then employ a greedy algorithm to choose the minimum‐weight spanning tree (MST). Though MST is a workhorse in applications, the mathematical properties of random MST are far less explored than those of UST. In this paper we develop tools for the quantitative study of random MST. We consider the standard case that the weights are drawn i.i.d. from a single distribution on the real numbers, as well as successive generalizations that lead to product measures, where the weights are independently drawn from arbitrary distributions.
Förderung
- National Science Foundation
- Simons Laufer Mathematical Sciences Institute, University of California Berkeley
Zitieren
APA
Babson, E., Duchin, M., Iseli, A., Poggi‐Corradini, P., Thurston, D., & Tucker‐Foltz, J. (2026). Models of Random Spanning Trees. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70063
Vancouver
Babson E, Duchin M, Iseli A, Poggi‐Corradini P, Thurston D, Tucker‐Foltz J. Models of Random Spanning Trees. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70063
BibTeX
@article{Babson2026,
author = {Babson, Eric and Duchin, Moon and Iseli, Annina and Poggi‐Corradini, Pietro and Thurston, Dylan and Tucker‐Foltz, Jamie},
title = {Models of Random Spanning Trees},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {68},
number = {3},
doi = {10.1002/rsa.70063}
}
EUVIMED