Name
Abstract | ||
|---|---|---|
Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a splicer, the union of a small number of spanning trees of a graph. We prove that for any bounded-degree n-vertex graph, the union of two uniformly random spanning trees approximates the expansion of the graph to within a factor of O(log n). For the complete graph, we prove that the union of two uniformly random spanning trees is an expander with high probability. For the random graph G(n,p), for p = Omega(log n/n), we give a randomized algorithm for constructing two spanning trees whose union is an expander. A closely related construction, which we call a selector, has similar properties. A random selector of a graph is obtained by starting with any spanning tree of the graph and adding a small number of random edges at each vertex. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/120890971 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
random spanning tree,random mapping,sparsification | Geometric graph theory,Discrete mathematics,Combinatorics,Tree (graph theory),Line graph,Random graph,Graph factorization,Null graph,Spanning tree,Butterfly graph,Mathematics | Journal |
Volume | Issue | ISSN |
43 | SP2 | 0097-5397 |
Citations | PageRank | References |
13 | 0.68 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan M. Frieze | 1 | 4837 | 787.00 |
| Navin Goyal | 2 | 13 | 1.02 |
| Luis Rademacher | 3 | 269 | 21.60 |
| Santosh Vempala | 4 | 3546 | 523.21 |