Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees.
David DurfeeJohn PeeblesRichard PengAnup B. RaoPublished in: FOCS (2017)
Keyphrases
- spanning tree
- edge disjoint
- minimum spanning tree
- minimum spanning trees
- minimum cost
- monte carlo
- low rank approximation
- random sampling
- least squares
- undirected graph
- depth first search
- singular value decomposition
- parameter space
- sampling methods
- weighted graph
- root node
- sampling strategy
- computational complexity
- sampling algorithm
- data points
- low dimensional