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

spectral graph theoryfast matrix multiplicationLaplacian matricesuniform 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

(6)

• Determinant-preserving sparsification of SDDM matrices
• Generation matrix: an embeddable matrix representation for hierarchical trees
• Sampling random spanning trees faster than matrix multiplication
• Exact sampling of spanning trees via fast-forwarded random walks
• Fast generation of random spanning trees and the effective resistance metric
• An almost-linear time algorithm for uniform random spanning tree generation

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)