18 citations · 28 across the 5 of their papers we have counts for
16 papers
-approximate fully dynamic densest subgraph: linear space and faster update time
Chandra Chekuri, Kent Quanrud
We consider the problem of maintaining a -approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dy…
Faster Algorithms for Rooted Connectivity in Directed Graphs
Chandra Chekuri, Kent Quanrud
We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and…
Fast Approximations for Rooted Connectivity in Weighted Directed Graphs
Kent Quanrud
We consider approximations for computing minimum weighted cuts in directed graphs. We consider both rooted and global minimum cuts, and both edge-cuts and vertex-cuts. For these pr…
Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems
Chandra Chekuri, Kent Quanrud
Li and Panigrahi, in recent work, obtained the first deterministic algorithm for the global minimum cut of a weighted undirected graph that runs in time . They introduced an…
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing…
Computing Circle Packing Representations of Planar Graphs
Sally Dong, Yin Tat Lee, Kent Quanrud
The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Pr…