A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Guy Even, Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticle

5 Scopus citations


We consider the following NP-hard problem: given a connected graph G=(V,ε) and a link set E on V disjoint to ε, find a minimum size subset of edges F ⊆ E such that (V,ε∪F) is 2-edge-connected. In G. Even et al. (2005) [2] we presented a 1.8-approximation for the problem. In this paper we improve the ratio to 1.5.

Original languageEnglish (US)
Pages (from-to)296-300
Number of pages5
JournalInformation Processing Letters
Issue number6
Publication statusPublished - Feb 15 2011


All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


  • Approximation algorithms
  • Laminar family
  • Tree augmentation

Cite this