Sensitivity Oracles for All-Pairs Mincuts

Surender Baswana, Abhyuday Pandey

Let $G=(V,E)$ be an undirected unweighted graph on $n$ vertices and $m$ edges. We address the problem of sensitivity oracle for all-pairs mincuts in $G$ defined as follows. Build a…