Computing edge-connectivity augmentation function in Õ( nm ) time

For a given undirected graph G = (V, E, c{sub G}) with edges weighted by nonnegative reals c{sub G} : E {r_arrow} R{sup +}, let {lambda}{sub G}(k) stand for the minimum amount of weights to be added to make G k-edge-connected, and G*(k) be the resulting graph obtained from G. This paper shows that function AG over the entire range k {element_of} [0, +{infinity}] has at most n - 1 break points ans it can be computed in O(nm + n{sup 2} log n) time, where n and m are the numbers of vertices and edges, respectively.