2018-01-01
Notes on growing a tree in a graph
Publication
Publication
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 | |
|---|---|
| Keywords | cheeger constant, first-passage percolation, graph degeneracy, graph genus, planar graphs, random spanning tree, treewidth |
| Persistent URL | dx.doi.org/10.1002/rsa.20828 |
| Journal | Random Structures and Algorithms |
| Citation |
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
|