Augmenting edge-connectivity over the entire range in (O)over-tilde(nm) time

For a given undirected graph G = (V, E, c(G)) with edges weighted by nonneg ative reals c(G): E --> R+, let Lambda(G)(k) stand for the minimum amount o f weights which needs to be added to make G k-edge-connected, and let G*(k) be the resulting graph obtained from G. This paper first shows that functi on Lambda(G) over the entire range k is an element of [0, + infinity] can b e computed in O(nm + n(2) log n) time, and then shows that all G*(k) in the entire range can be obtained from O(n log n) weighted cycles, and such cyc les can be computed in O(nm + n(2) log n) time, where n and m are the numbe rs of vertices and edges, respectively. (C) 1999 Academic Press.