Expanders via Random Spanning Trees

DOI10.1137/120890971MaRDI QIDQ5494927zbMATH OpenOpenAlexWikidataFDO

Authors Navin Goyal, Luis Rademacher, Alan Frieze, Santosh S. Vempala

Publication date 30 July 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.2844

zbMATH Keywords

sparsificationrandom mappingrandom spanning tree

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Expanders via random spanning trees
• Spanning trees in random graphs
• scientific article; zbMATH DE number 747032
• Spanning trees in randomly perturbed graphs
• Random Schreier graphs and expanders
• Expanders with respect to Hadamard spaces and random graphs
• Spanning trees in random satisfiability problems
• Embedding spanning trees in random graphs
• Expanders with respect to Hadamard spaces and random graphs (extended abstract)
• On random minimum length spanning trees

Cited in

(10)

• Spanders: distributed spanning expanders
• scientific article; zbMATH DE number 7650133 (Why is no real title available?)
• Expanders Are Universal for the Class of All Spanning Trees
• Tangled paths: a random graph model from Mallows permutations
• The union of independent USFs on \(\mathbb{Z}^d\) is transient
• Expanders via random spanning trees
• Scalable expanders: exploiting hierarchical random wiring
• On random k-out subgraphs of large graphs
• scientific article; zbMATH DE number 1559568 (Why is no real title available?)
• Physical expander in virtual tree overlay

This page was built for publication: Expanders via Random Spanning Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494927)