28 citations · 88 across the 15 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.DS2016
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, John Peebles +2
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in time (The $\tilde{…
cs.DS2016★ 22 cited
On Fully Dynamic Graph Sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis +2
We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polyl…