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+n2log 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}.

Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n2log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.

Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v1,v2,...,vn of vertices in V such that, for each i = 2,3,...,n - 1, set {v1,v2,...,vi} is an i-maximizer. We give an O(mn + n2log n) time algorithm for finding such an ordering and then show an application to the source location problem.