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

Abstract

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
Volume111
Issue number6
DOIs
Publication statusPublished - Feb 15 2011

    Fingerprint

All Science Journal Classification (ASJC) codes

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

Keywords

  • Approximation algorithms
  • Laminar family
  • Tree augmentation

Cite this