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.

, , , , , ,
Random Structures and Algorithms
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