A fast algorithm for optimally increasing the edge-connectivity

Dalit Naor, Dan Gusfield, Charles U. Martel · Annual Symposium on Foundations of Computer Science · 2002

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta , the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta . A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1>

Cited by 64 works. doi:10.1109/fscs.1990.89592

Authors

References