Tutte seminar - Laszlo Vegh

Friday, September 30, 2011 3:30 pm - 4:30 pm EDT (GMT -04:00)

Augmenting undirected node-connectivity by one

Speaker: Laszlo Vegh
Affiliation: GeorgiaTech
Room: Mathematics & Computer Building (MC) 5158


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. 

In my talk, 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.