research
∙
04/13/2023
Beyond the Quadratic Time Barrier for Network Unreliability
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability ...
share
research
∙
11/10/2022
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
We give an almost-linear time algorithm for the Steiner connectivity aug...
research
∙
05/10/2022
Edge Connectivity Augmentation in Near-Linear Time
We give an Õ(m)-time algorithm for the edge connectivity augmentation pr...
research
∙
11/17/2021
Minimum Cuts in Directed Graphs via Partial Sparsification
We give an algorithm to find a minimum cut in an edge-weighted directed ...
research
∙
11/03/2021
Augmenting Edge Connectivity via Isolating Cuts
We give an algorithm for augmenting the edge connectivity of an undirect...
research
∙
04/16/2021
Minimum Cuts in Directed Graphs via √(n) Max-Flows
We give an algorithm to find a mincut in an n-vertex, m-edge weighted di...
research
∙
11/27/2019