A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)

Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov

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

1 Scopus citations

Abstract

We consider the following problem: given a connected graph G = (V, εE) and an additional edge set E, find a minimum size subset of edges F ⊆E suchth at (V,ε ∪F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings
EditorsLuca Trevisan, Klaus Jansen, Michel Goemans, Jose D. P. Rolim
PublisherSpringer Verlag
Pages90-101
Number of pages12
ISBN (Electronic)3540424709
StatePublished - 2015
Externally publishedYes
Event4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 - Berkeley, United States
Duration: Aug 18 2001Aug 20 2001

Publication series

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

Other

Other4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001
Country/TerritoryUnited States
CityBerkeley
Period8/18/018/20/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set (Extended abstract)'. Together they form a unique fingerprint.

Cite this