Access Restriction

Author Khuller, Samir ♦ Vishkin, Uzi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword 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 $\textit{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.We also consider the case where the graph has edge weights. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a $\textit{k}-edge$ connected spanning subgraph. This improves an approximation factor of 3 for $\textit{k}$ = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any $\textit{k}$ (with an increased running time though).
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 41
Issue Number 2
Page Count 22
Starting Page 214
Ending Page 235

Open content in new tab

   Open content in new tab
Source: ACM Digital Library