93 citations · 537 across the 73 of their papers we have counts for
11 papers · 1 filter
Vertex Sparsifiers for c-Edge Connectivity
Yang P. Liu, Richard Peng, Mark Sellke
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve all edge-connectivity values up to c between a set of k terminal vertices, where f(c) is a function that on…
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
Yu Gao, Jason Li, Danupon Nanongkai +3
We study deterministic algorithms for computing graph cuts, with focus on two fundamental problems: balanced sparse cut and -vertex connectivity for small ($k=O(\polylog n)$…
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…
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Julia Chuzhoy, Yu Gao, Jason Li +3
We consider the classical Minimum Balanced Cut problem: given a graph , compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number…
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
David Durfee, Laxman Dhulipala, Janardhan Kulkarni +3
In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In thi…
Dynamic Optimality Refuted -- For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild +1
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys st…