We study the height of a spanning tree T of a graph G obtained by starting with a single vertex of G and repeatedly selecting, uniformly at random, an edge of G with exactly one endpoint in T and adding this edge to T.
Additional Metadata | |
---|---|
cheeger constant, first-passage percolation, graph degeneracy, graph genus, planar graphs, random spanning tree, treewidth | |
dx.doi.org/10.1002/rsa.20828 | |
Random Structures and Algorithms | |
Organisation | School of Computer Science |
Devroye, L. (Luc), Dujmović, V, Frieze, A. (Alan), Mehrabian, A. (Abbas), Morin, P, & Reed, B. (Bruce). (2018). Notes on growing a tree in a graph. Random Structures and Algorithms. doi:10.1002/rsa.20828
|