### 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 language | English (US) |
---|---|

Pages (from-to) | 296-300 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 111 |

Issue number | 6 |

DOIs | |

State | Published - Feb 15 2011 |

### Fingerprint

### 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

*Information Processing Letters*,

*111*(6), 296-300. https://doi.org/10.1016/j.ipl.2010.12.010

}

*Information Processing Letters*, vol. 111, no. 6, pp. 296-300. https://doi.org/10.1016/j.ipl.2010.12.010

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

Research output: Contribution to journal › Article

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 -