Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm

Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou

We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic algorithm explic…