Biconnectivity approximations and graph carvingsBiconnectivity approximations and graph carvings

Access Restriction
Subscribed

 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

Source: ACM Digital Library