Sampling random spanning trees faster than matrix multiplication

DOI10.1145/3055399.3055499zbMath1370.68122arXiv1611.07451OpenAlexW2552685338MaRDI QIDQ4978019

Sushant Sachdeva, Rasmus Kyng, John Peebles, David Durfee, Anup B. Rao

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.07451

zbMATH Keywords

random spanning treessampling algorithmapproximate Schur complementgraph sparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Models of random subtrees of a graph ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Unnamed Item ⋮ Graph Clustering using Effective Resistance ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ A queueing network-based distributed Laplacian solver ⋮ A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees ⋮ A BWT-based algorithm for random de Bruijn sequence construction ⋮ Unnamed Item ⋮ Distance-Preserving Graph Contractions ⋮ Electrical flows over spanning trees

This page was built for publication: Sampling random spanning trees faster than matrix multiplication