Events by date

Increasing connectivity of a graph from 1 to 2

Speaker: Guy Kortsarz Affiliation: Rutgers University Room: Mathematics & Computer Building (MC) 5158

Abstract:

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').