Conference Paper,
Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
Contributors
Thorup M.
0000-0001-5237-1709
[2]
Affiliations
- [1] University of Illinois at Chicago [NORA names: United States; America, North; OECD];
- [2] University of Copenhagen [NORA names: KU University of Copenhagen; University; Denmark; Europe, EU; Nordic; OECD]
Abstract
We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n). Previously, the best update time was O(√n) for any c > 2 and c = O(log n) [28].
