3 papers
cs.DS2019
Fully Dynamic Spectral Vertex Sparsifiers and Applications
David Durfee, Yu Gao, Gramoz Goranci +1
We study \emph{dynamic} algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals of our choice. Such objects preserve pairwise resist…
cs.DS2019
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…
cs.DS2017
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…