Expanders via random spanning trees

MaRDI QIDQ4633869zbMATH OpenFDO

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

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
• 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

Cited in

(13)

• Geometric bijections between spanning trees and break divisors
• Scalable expanders: exploiting hierarchical random wiring
• Constructing near spanning trees with few local inspections
• Physical expander in virtual tree overlay
• Spanders: distributed spanning expanders
• Expanders via local edge flips
• Expanders Are Universal for the Class of All Spanning Trees
• Determinant-preserving sparsification of SDDM matrices
• Expanders via Random Spanning Trees
• Electric routing and concurrent flow cutting
• Coboundary expansion for the union of determinantal hypertrees
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• AC(k): robust solution of Laplacian equations by randomized approximate Cholesky factorization

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)