TY - GEN

T1 - Approximation algorithms for graph augmentation

AU - Khuller, Samir

AU - Thurimella, Ramakrishna

PY - 1992/1/1

Y1 - 1992/1/1

N2 - We study the problem of increasing the connectivity1 of a graph at an optimal cost. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optimal. Previous algorithms either do not take edge costs into consideration, or run slower than our algorithm. Our algorithm takes as input an undirected graph Go= (V, E0) on n vertices, that is not necessarily connected, and a set Feasible of m weighted edges on V, and outputs a subset Aug of edges which when added to Go make it 2-connected. The weight of Aug, when Go is initially connected, is no more than twice the weight of the least weight subset of edges of Feasible that increases the connectivity to 2. The running time of our algorithm is O(m+n log n). We also study the problem of increasing the edge connectivity of any graph G, to k, within a factor of 2 (for any k > 0). The running time of this algorithm is O(nk log n(m + n log n)). We observe that when k is odd we can use different techniques to obtain an approximation factor of 2 for increasing edge connectivity from k to (k+1) in O(kn2) time.

AB - We study the problem of increasing the connectivity1 of a graph at an optimal cost. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optimal. Previous algorithms either do not take edge costs into consideration, or run slower than our algorithm. Our algorithm takes as input an undirected graph Go= (V, E0) on n vertices, that is not necessarily connected, and a set Feasible of m weighted edges on V, and outputs a subset Aug of edges which when added to Go make it 2-connected. The weight of Aug, when Go is initially connected, is no more than twice the weight of the least weight subset of edges of Feasible that increases the connectivity to 2. The running time of our algorithm is O(m+n log n). We also study the problem of increasing the edge connectivity of any graph G, to k, within a factor of 2 (for any k > 0). The running time of this algorithm is O(nk log n(m + n log n)). We observe that when k is odd we can use different techniques to obtain an approximation factor of 2 for increasing edge connectivity from k to (k+1) in O(kn2) time.

UR - http://www.scopus.com/inward/record.url?scp=84994613290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994613290&partnerID=8YFLogxK

U2 - 10.1007/3-540-55719-9_85

DO - 10.1007/3-540-55719-9_85

M3 - Conference contribution

AN - SCOPUS:84994613290

SN - 9783540557197

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 330

EP - 341

BT - Automata, Languages and Programming - 19th International Colloquium, Proceedings

A2 - Kuich, Werner

PB - Springer Verlag

T2 - 19th International Colloquium on Automata, Languages, and Programming, ICALP 1992

Y2 - 13 July 1992 through 17 July 1992

ER -