Augmenting Undirected Node-Connectivity by One
Author:
- László A. VéghLVLászló A. Végh
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 25 (2) , 695-718
Abstract
We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum-cost version for node-induced cost functions.Keywords
This publication has 16 references indexed in Scilit:
- Rooted -connections in digraphsDiscrete Applied Mathematics, 2009
- An algorithm to increase the node-connectivity of a digraph by oneDiscrete Optimization, 2008
- Independence free graphs and vertex connectivity augmentationJournal of Combinatorial Theory, Series B, 2005
- On Four-Connecting a Triconnected GraphJournal of Algorithms, 2000
- Fast Algorithms for k-Shredders and k-Node Connectivity AugmentationJournal of Algorithms, 1999
- Covering a symmetric poset by symmetric chainsCombinatorica, 1997
- Minimal Edge-Coverings of Pairs of SetsJournal of Combinatorial Theory, Series B, 1995
- Augmenting Graphs to Meet Edge-Connectivity RequirementsSIAM Journal on Discrete Mathematics, 1992
- Generalized polymatroids and submodular flowsMathematical Programming, 1988
- Augmentation ProblemsSIAM Journal on Computing, 1976