Augmenting undirected node-connectivity by one

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.

Authors

• László A. Végh

Keywords

• connectivity augmentation
• node-connectivity