93 citations · 537 across the 73 of their papers we have counts for
5 papers · 1 filter
On Computing Min-Degree Elimination Orderings
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
We study faster algorithms for producing the minimum degree ordering used to speed up Gaussian elimination. This ordering is based on viewing the non-zero elements of a symmetric p…
Optimal Offline Dynamic -Edge/Vertex Connectivity
Richard Peng, Bryce Sandlund, Daniel D. Sleator
We give offline algorithms for processing a sequence of and edge and vertex connectivity queries in a fully-dynamic undirected graph. While the current best fully-dynamic o…
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
David Durfee, John Peebles, Richard Peng +1
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant o…
Concave Flow on Small Depth Directed Networks
Tung Mai, Richard Peng, Anup B. Rao +1
Small depth networks arise in a variety of network related applications, often in the form of maximum flow and maximum weighted matching. Recent works have generalized such methods…
Density Independent Algorithms for Sparsifying -Step Random Walks
Gorav Jindal, Pavel Kolev, Richard Peng +1
We give faster algorithms for producing sparse approximations of the transition matrices of -step random walks on undirected, weighted graphs. These transition matrices also for…