Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time

For a given undirected graphG = (V, E, c_G) with edges weighted by nonnegative realsc_G:E → R ⁺ , let Λ_G(k) stand for the minimum amount of weights which needs to be added to makeG k-edge-connected, and letG*(k) be the resulting graph obtained fromG. This paper first shows that function Λ_Gover the entire rangek [0, +∞] can be computed inO(nm + n² log n) time, and then shows that allG*(k) in the entire range can be obtained fromO(n log n) weighted cycles, and such cycles can be computed inO(nm + n² log n) time, wherenandmare the numbers of vertices and edges, respectively.     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000