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 Citations (Scopus)

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
StatePublished - Feb 15 2011

Fingerprint

Edge-connectivity
Approximation algorithms
NP-hard Problems
Connected graph
Approximation Algorithms
Computational complexity
Disjoint
Subset
Approximation
Graph in graph theory

All Science Journal Classification (ASJC) codes

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

Keywords

  • Approximation algorithms
  • Laminar family
  • Tree augmentation

Cite this

@article{9a8061fe5bd14fb38897dc72aa98dab8,
title = "A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2",
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.",
keywords = "Approximation algorithms, Laminar family, Tree augmentation",
author = "Guy Even and Guy Kortsarz and Zeev Nutov",
year = "2011",
month = "2",
day = "15",
doi = "10.1016/j.ipl.2010.12.010",
language = "English (US)",
volume = "111",
pages = "296--300",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "6",

}

A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. / Even, Guy; Kortsarz, Guy; Nutov, Zeev.

In: Information Processing Letters, Vol. 111, No. 6, 15.02.2011, p. 296-300.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Even, Guy

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2011/2/15

Y1 - 2011/2/15

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Laminar family

KW - Tree augmentation

UR - http://www.scopus.com/inward/record.url?scp=78650268807&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650268807&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.12.010

DO - 10.1016/j.ipl.2010.12.010

M3 - Article

VL - 111

SP - 296

EP - 300

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 6

ER -