M.F. Cowlishaw
IBM Systems Journal
Let G = (V, E) be an undirected, unweighted graph with n nodes, m edges and edge connectivity λ. Given an input parameter δ, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge connectivity is increased by δ. In this paper, we present a solution to this problem which runs in O(δ2nm + δ3n2 + nF(G)), where F(G) is the time to perform one maximum flow on G. In fact, our solution gives the optimal augmentation for every δ′, 1 ≤ δ′ ≤ δ, in the same time bound. By introducing minor modifications to the solution, we can solve the problem without knowing δ in advance, and we can also solve the node-weighted version and the degree-constrained version of the problem. If δ = 1, then our solution is particularly simple; it runs in O(nm) time, and it is a natural generalization of the algorithm in [K. Eswaran and R. E. Tarjan, SIAM J. Comput., 5 (1976), pp. 653-665] for the case where λ + δ = 2. We also solve the converse problem in the same time bound: given an input number k, increase the connectivity of G as much as possible by adding at most k edges. Our solution makes extensive use of the structure of particular sets of cuts.
M.F. Cowlishaw
IBM Systems Journal
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Eric Price, David P. Woodruff
FOCS 2011
Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design