Fast Generation of Random Spanning Trees and the Effective Resistance Metric

DOI10.1137/1.9781611973730.134zbMath1372.68213arXiv1501.00267OpenAlexW1601422707MaRDI QIDQ5363075

Jakub Tarnawski, Damian Straszak, Aleksander Mądry

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ A Spectral Approach to Network Design ⋮ 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 ⋮ A queueing network-based distributed Laplacian solver for directed graphs ⋮ A queueing network-based distributed Laplacian solver ⋮ Unnamed Item ⋮ Linking and cutting spanning trees

This page was built for publication: Fast Generation of Random Spanning Trees and the Effective Resistance Metric