Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex
Hiroshi Nagamochi · IEICE Transactions on Information and Systems · 2007
We consider an edge-weighted graph G with a designated vertex v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn + n2 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 {v0, u}.