Friday, March 20, 2009
3:30 pm, MC 5158

Guy Kortsarz
Rutgers University

Inceasing connectivity of a graph from 1 to 2

Given an unweighted graph G(V,E) and a set F\subseteq V\times V the goal is to find a minimum SIZE F'\subset F such that G(V,E+F') is 2 edge-connected, namely, every edge lies in a cycle in G(V,E+F').
This problem is one of the most basic problems in connectivity augmentation. We have a (somewhat complex) 1.5 approximation algorithm for the problem (namely an algorithm that for every instance outputs a solution of size no more than 1.5 times the optimum solution for this instance).
In this talk we will give some of the details of a significantly simpler 1.8 approximation for the problem. The talk is self contained.