On 2-Connected Subgraphs

Adrian Vetta


March 29,
refreshments at 3:45pm


The task of finding small spanning graphs of a prescribed connectivity is a fundamental problem in network optimization. Unfortunately, it is also a hard probem. I will present a 4/3-approximation algorithm for the Minimum 2-Edge Connected Subgraph problem in undirected graphs. This result verifies one implication of the well known "4/3-Conjecture" regarding the subtour relaxation for the Travelling Salesman Problem. Our main tools are techniques from matching theory and a decomposition theorem that allows us to focus upon relatively simple graphs. For directed graphs I will outline an approximation algorithm for the Minimum Strongly Connected Subgraph problem with a 3/2-approximation guarantee. These factors improve upon the previously best known values (1.42 and 1.61 resp.). This is work with Santosh Vempala.

Speaker's Contact Info: avetta(at-sign)math.mit.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on February 18, 2000 at 03:23 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.