21 citations · 64 across the 21 of their papers we have counts for
31 papers
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai +3
In the -edge-connected spanning subgraph (ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to link failures: Given an -nod…
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
Yaowei Long, Thatchaphol Saranurak
We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-un…
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel, Haim Kaplan, Yishay Mansour +3
A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain…
Deterministic Weighted Expander Decomposition in Almost-linear Time
Jason Li, Thatchaphol Saranurak
In this note, we study the expander decomposition problem in a more general setting where the input graph has positively weighted edges and nonnegative demands on its vertices. We…
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
We give an -time algorithm for finding - min-cuts for all pairs of vertices and in a simple, undirected graph on vertices. We do so by constructing a…
Minimum Cuts in Directed Graphs via Max-Flows
Ruoxu Cen, Jason Li, Danupon Nanongkai +2
We give an algorithm to find a mincut in an -vertex, -edge weighted directed graph using calls to any maxflow subroutine. Using state of the art maxflow…