Generating random spanning trees via fast matrix multiplication

DOI10.1007/978-3-662-49529-2_39MaRDI QIDQ2802966zbMATH OpenOpenAlexFDO

Authors Keyulu Xu, Nicholas Harvey

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-49529-2_39

zbMATH Keywords

fast matrix multiplicationLaplacian matricesspectral graph theoryuniform spanning trees

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Sampling random spanning trees faster than matrix multiplication
• An almost-linear time algorithm for uniform random spanning tree generation
• scientific article; zbMATH DE number 1256746
• Fast generation of random spanning trees and the effective resistance metric
• Linking and cutting spanning trees

Cited in

(8)

• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• Sampling random spanning trees faster than matrix multiplication
• Determinant-preserving sparsification of SDDM matrices
• An almost-linear time algorithm for uniform random spanning tree generation
• Fast generation of random spanning trees and the effective resistance metric
• Generation matrix: an embeddable matrix representation for hierarchical trees
• Exact sampling of spanning trees via fast-forwarded random walks
• Quantum speedup for sampling random spanning trees

This page was built for publication: Generating random spanning trees via fast matrix multiplication

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