# Biconnectivity approximations and graph carvings

Title | Biconnectivity approximations and graph carvings |

Publication Type | Journal Articles |

Year of Publication | 1994 |

Authors | Khuller S, Vishkin U |

Journal | Journal of the ACM (JACM) |

Volume | 41 |

Issue | 2 |

Pagination | 214 - 235 |

Date Published | 1994/03// |

ISBN Number | 0004-5411 |

Keywords | biconnectivity, connectivity, sparse subgraphs |

Abstract | A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard.We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity, our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP-hard as well. |

URL | http://doi.acm.org/10.1145/174652.174654 |

DOI | 10.1145/174652.174654 |