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
PDFNot 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.
CopyrightThe 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.

To the list of the CS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion
admin