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 |

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.

To the list of the CS technical reports of 1996

To the main CS technical reports page