Notes on growing a tree in a graph

Devroye, Luc; Dujmović, Vida; Frieze, Alan; Mehrabian, Abbas; Morin, Pat; Reed, Bruce

doi:10.1002/rsa.20828

Devroye, L. (Luc), V. Dujmović (Vida), Frieze, A. (Alan), Mehrabian, A. (Abbas), P. Morin (Pat) and Reed, B. (Bruce)

2018

Notes on growing a tree in a graph

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	doi.org/10.1002/rsa.20828
Journal	Random Structures and Algorithms
Organisation	School of Computer Science
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	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

Notes on growing a tree in a graph

Publication

Publication

Notes on growing a tree in a graph

Publication

Publication

Workflow

Workflow

Add Content