Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

Wenyu Jin, Xiaorui Sun, Mikkel Thorup

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…