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
- Multi-Terminal Network Flows
- Network Flow and Testing Graph Connectivity
- Augmentation Problems
- Introduction to Algorithms: A Creative Approach
- Approximation Algorithms for Several Graph Augmentation Problems
- Determining edge connectivity in 0(nm)
- A Graph Theoretic Approach to Statistical Data Security
- Augmenting graphs to meet edge-connectivity requirements
- Connectivity and edge-disjoint spanning trees
- Edge-connectivity augmentation problems