Cristina Gomes Fernandes (cris@ime.usp.br)
6a. feira - 17 de outubro - 14 horas
Sala 242--A
Abstract: Consider the minimum $k$-edge-connected spanning subgraph problem: given a positive integer $k$ and a $k$-edge-connected graph $G$, find a $k$-edge-connected spanning subgraph of $G$ with minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algorithm with a performance ratio smaller than 2 for all $k$. They proved an upper bound of 1.85 for the performance ratio of their algorithm. We improve their analysis, proving that the performance ratio of their algorithm is smaller than 1.7 for large enough $k$, and that it is at most 1.75 for all $k$. Last, we show that the minimum 2-edge-connected spanning subgraph problem is MAX SNP-hard.