Approximating Directed Connectivity in Almost-Linear Time

Kent Quanrud

We present randomized algorithms that compute $(1+\hat{I}\mu )$-approximate minimum global edge and vertex cuts in weighted directed graphs in $O({\log }^4(n)/\hat{I}\mu )$ and $O({\log }^5(n)/\hat{I}\mu )$ sing…