Date:

Monday , September 17, 2001

Speaker:

Hal Gabow

Affiliation:

Computer Science Department, University of Colorado, Boulder

e-mail:

hal@cs.colorado.edu

Title:

An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph

Abstract:

An important network design problem is the construction of cheap yet robust networks. This can be modelled as finding a spanning subgraph of a given graph that achieves a given target connectivity with the fewest possible number of edges. Even the simplest versions of this problem generalize the Travelling Salesman Problem and so are NP-hard. Thus many approximation algorithms have been developed.

The first part of the talk surveys the basic definitions and approaches to this so-called "k-ECSS problem". This survey emphasizes the theme, approximation algorithm = structural idea + lower bound + tight example. The second part presents a new algorithm that achieves a 3/2 approximation ratio for 3-ECSS, i.e., we must find a subgraph that won't break up when 2 edges fail. The best previous approximation ratio was 5/3. Our approach is based on Hassler Whitney's 1932 idea of ear decomposition.