The corresponding graph problem is to make a given (undirected or directed) graph k-(edge or vertex)-connected by adding a set of new edges with minimum cost/size for some connectivity requirement k. The weighted versions are usually NP-hard. For some of them efficient approximation algorithms are known.
In this talk we will focus on the unweighted case where the number of new edges is to be minimized. There exist polynomial algorithms for most of these problems. The goal is to present recent results and some open questions in this area.
(A graph (digraph) G=(V,E) is k-vertex-connected, if |V| >= k+1 and G-X is connected (strongly connected) for any subset X of V with |X| <= k-1. A graph (digraph) is said to be k-edge-connected, if G-F is connected (strongly connected) for any subset F of E with |F| <= k-1.)