Augmenting graphs to meet edge-connectivity requirements
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 708-718 vol.2
- https://doi.org/10.1109/fscs.1990.89593
Abstract
The problem of determining the minimum number gamma of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair (u,v) of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for gamma is derived, and a polynomial-time algorithm for computing gamma is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k>or=1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs.Keywords
This publication has 12 references indexed in Scilit:
- Integer Solution to Synthesis of Communication NetworksMathematics of Operations Research, 1992
- Generalized polymatroids and submodular flowsMathematical Programming, 1988
- Edge-connectivity augmentation problemsJournal of Computer and System Sciences, 1987
- GENERALIZED POLYMATROIDSPublished by Elsevier ,1984
- Konstruktion aller n-fach kantenzusammenhängenden DigraphenEuropean Journal of Combinatorics, 1982
- How to make a digraph strongly connectedCombinatorica, 1981
- A Minimax Theorem for Directed GraphsJournal of the London Mathematical Society, 1978
- A Reduction Method for Edge-Connectivity in GraphsPublished by Elsevier ,1978
- Augmentation ProblemsSIAM Journal on Computing, 1976
- Minimal k‐arc connected graphsNetworks, 1971