Xiaorui Sun

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

2024 · arXiv (Cornell University)

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 …