# Technical Report CS0886

 TR#: CS0886 Class: CS Title: Finding minimum weight $k$-vertex connected spanning subgraphs: approximation algorithms with factor 2 for $k=3$ and factor 3 for $k=4,5$ Authors: Ye. Dinitz and Z. Nutov PDF Not Available Abstract: The problem of finding a minimum weight $k$-vertex connected spanning subgraph is considered. For $k>1$, this problem is known to be NP-hard. Combining properties of inclusion-minimal $k$-vertex connected graphs and of $k$-out-connected graphs (i.e., graphs which contain a vertex from which there are $k$ internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of $k$. \begin{itemize} \item[(i)] For $k=3$, we give an algorithm with approximation factor $2$. This improves the best previously known factor $3$. \item[(ii)] For $k = 4$ and $k=5$, we give an algorithm with approximation factor $3$. This improves the best previously known factors $4\frac{1}{6}$ and $4\frac{17}{30}$, respectively. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1996/CS/CS0886), rather than to the URL of the PDF files directly. The latter URLs may change without notice.