![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
Author: Fernandes C.G.
Publisher: Academic Press
ISSN: 0196-6774
Source: Journal of Algorithms, Vol.28, Iss.1, 1998-07, pp. : 105-124
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
Consider the minimum size k-edge-connected spanning subgraph problem: given a positive integer k and a k-edge-connected graph G, find a k-edge-connected spanning subgraph of G with the minimum number of edges. This problem is known to be NP-complete. Khuller and Raghavachari presented the first algorithm which, for all k, achieves a performance ratio smaller than a constant which is less than two. They proved an upper bound of 1.85 for the performance ratio of their algorithm. Currently, the best known performance ratio for the problem is 1 + 2/(k + 1), achieved by a slower algorithm of Cheriyan and Thurimella. In this article, we improve Khuller and Raghavachari's analysis, proving that the performance ratio of their algorithm is smaller than 1.7 for large enough k, and that it is at most 1.75 for all k. Second, we show that the minimum size 2-edge-connected spanning subgraph problem is MAX SNP-hard. Copyright 1998 Academic Press.
Related content
![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
An improved approximation ratio for the minimum latency problem
Mathematical Programming, Vol. 82, Iss. 1, 1998-06 ,pp. :
![](/images/ico/ico_close.png)
![](/images/ico/ico5.png)
Finding 2-edge connected spanning subgraphs
By Huh W.T.
Operations Research Letters, Vol. 32, Iss. 3, 2004-05 ,pp. :