@inproceedings{0293df4b2a484fbcbdc92fcc1b173f43,

title = "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)",

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.",

author = "Guy Even and Jon Feldman and Guy Kortsarz and Zeev Nutov",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001; 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 ; Conference date: 18-08-2001 Through 20-08-2001",

year = "2015",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "90--101",

editor = "Luca Trevisan and Klaus Jansen and Michel Goemans and Rolim, {Jose D. P.}",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

address = "Germany",

}