TY - GEN

T1 - Approximation algorithms for graph augmentation

AU - Khuller, Samir

AU - Thurimella, Ramakrishna

N1 - Funding Information:
Augmenting the connectivity of communication networks is increasingly becoming important to provide reliable means of communication. Informally, the problem is the following: we have a "current" network, and we wish to increase the connectivity of the network by adding edges. Each feasible edge has an associated weight, and we want to achieve the desired connectivity by adding the least total weight of edges. The Weighted Augmentation Problem: Consider a graph G = (V, E) with a weight wi >_ 0 on edge ei, where E is the set of feasible edges. We are also given a "current" network, the graph Go(V, Eo) that is a subgraph of G. The goal is to add a minimum weight set of edges Aug, to Go, such that the resulting graph is k-connected for a given k. The edges that we axe permitted to add, are required to be edges from the graph G (the feasibility graph). If E0 = and k = 1 then the problem is that of finding a minimum weight spanning tree on V. It is well known that this problem can be solved very efficiently. For k > 1, the problem turns out to be NP-hard. We will study approximation algorithms for the general problem. Our Results: Let m and n denote the number of edges and the number of vertices, respectively, of the input graph. In this paper we provide a simple algorithm (for k = 2) that produces an approximation within a factor of 2 in O(m + nlogn) time. Note that for sparse networks the algorithm is faster by a factor of n2/mo (The previous algorithm for the problem is due to *Institute for Advanced Computer Studies (UMIACS), The University of Maryland at College Park, College Park, MD 20742. This work is partially supported by NSF grants CCR-8906949, CCR-9103135 and CCR-9111348. IDepartment of Mathematics and Computer Science, University of Denver, Denver, CO 80208. Part of this work was done while this author was with UMIACS. IConnectlvity refers to both edge and vertex connectivity throughout the paper unless stated explicitly otherwise.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

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 -