Increasing connectivity of a graph from 1 to 2
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1