Expanders via random spanning trees

zbMATH Open1421.68100MaRDI QIDQ4633869FDOQ4633869

Authors: Navin Goyal, Luis Rademacher, Santosh S. Vempala 

Publication date: 6 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=1496834

Recommendations

• Expanders via Random Spanning Trees
• Expanders are universal for the class of all spanning trees
• Existence and Construction of Edge-Disjoint Paths on Expander Graphs
• Expanders Are Universal for the Class of All Spanning Trees
• A general framework for graph sparsification

Mathematics Subject Classification ID

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

Cited In (11)

• Expanders via local edge flips
• Spanders: distributed spanning expanders
• Expanders via Random Spanning Trees
• Expanders Are Universal for the Class of All Spanning Trees
• Electric routing and concurrent flow cutting
• Determinant-preserving sparsification of SDDM matrices
• Scalable expanders: exploiting hierarchical random wiring
• Coboundary expansion for the union of determinantal hypertrees
• Geometric bijections between spanning trees and break divisors
• Physical expander in virtual tree overlay
• Constructing near spanning trees with few local inspections

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 Q4633869)