Computing a minimum cut in a graph with dynamic edges incident to a designated vertex
We consider an edge-weighted graph G with a designated vertex v(0) such that weights of edges incident to v(0) may increase or decrease. We show that, with an O(mn + n(2) log n) time preprocessing, a minimum cut of the current G can be computed in O(log n) time per update of weight of any edge (v(0), u).
dynamic graph edge-connectivity extreme vertex set graph algorithm