CATS Seminar
Capital Area Theory Seminar
http://www.umiacs.umd.edu/users/liberato/cats.html
Approximating minimum-size k-edge connected spanning subgraphs
Joseph Cheriyan
Dept. of Combinatorics & Optimization
University of Waterloo
Waterloo, Canada
Wednesday, March 24, 1999, 2 p.m.
AVW 2120
Abstract
The talk will discuss some recent results on approximation algorithms for the NP-hard problem of finding a minimum-size k-edge connected spanning subgraph of a given graph. By exploiting results from matching theory, approximation guarantees of 3/2 or less are attained. Also, the relation to the TSP 4/3 conjecture will be discussed.
(Joint work with: R.Thurimella, A.Sebo, Z.Szigeti)
Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)
The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged