Approximation algorithms for graph augmentation

Samir Khuller, Ramakrishna Thurimella

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 19th International Colloquium, Proceedings
EditorsWerner Kuich
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540557197
StatePublished - 1992
Event19th International Colloquium on Automata, Languages, and Programming, ICALP 1992 - Wien, Austria
Duration: Jul 13 1992Jul 17 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume623 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Colloquium on Automata, Languages, and Programming, ICALP 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Approximation algorithms for graph augmentation'. Together they form a unique fingerprint.

Cite this