### Augmenting undirected node-connectivity by one - Part II

- Series
- Graph Theory Seminar
- Time
- Thursday, March 29, 2012 - 12:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Laszlo Vegh – College of Computing, Georgia Tech

In the node-connectivity augmentation problem, we want to add a minimum
number of new edges to an undirected graph to make it k-node-connected.
The complexity of this question is still open, although the analogous questions
of both directed and undirected edge-connectivity and directed
node-connectivity augmentation are known to be polynomially solvable.
I present a min-max formula and a polynomial time algorithm for the
special case when the input graph is already (k-1)-connected. The formula has
been conjectured by Frank and Jordan in 1994.
In the first lecture, I presented previous results on the other connectivity augmentation variants.
In the second part, I shall present my min-max formula and the main ideas of the proof.