16 citations · 61 across the 32 of their papers we have counts for
9 papers · 1 filter
Planar Diameter via Metric Compression
Jason Li, Merav Parter
We develop a new approach for distributed distance computation in planar graphs that is based on a variant of the metric compression problem recently introduced by Abboud et al. [S…
The Karger-Stein Algorithm is Optimal for -cut
Anupam Gupta, Euiwoong Lee, Jason Li
In the -cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into connected components. Algorithms…
Faster Parallel Algorithm for Approximate Shortest Path
Jason Li
We present the first work, time algorithm in the PRAM model that computes -approximate single-source shortest paths on weighted, u…
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)$…
Faster Minimum k-cut of a Simple Graph
Jason Li
We consider the (exact, minimum) -cut problem: given a graph and an integer , delete a minimum-weight set of edges so that the remaining graph has at least connected comp…
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…