Research My IBM Log in
Paper

A fast algorithm for optimally increasing the edge connectivity

Abstract

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.

Semiconductors Artificial Intelligence Quantum Computing Hybrid Cloud About Publications Blog Events Careers Contact Research Topics People Projects Newsletter X LinkedIn YouTube RSS Contact IBM Privacy Terms of use Accessibility