12 citations · 17 across the 5 of their papers we have counts for
5 papers
Flowless: Extracting Densest Subgraphs Without Flow Computations
Digvijay Boob, Yu Gao, Richard Peng +4
We propose a simple and computationally efficient method for dense subgraph discovery, which is a classic problem both in theory and in practice. It is well known that dense subgra…
Near-Optimal Fully Dynamic Densest Subgraph
Saurabh Sawlani, Junxing Wang
We give the first fully dynamic algorithm which maintains a -approximate densest subgraph in worst-case time per update. Dense subgraph discove…
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides a…
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…