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

DOI10.1016/j.ipl.2010.12.010zbMath1260.68464OpenAlexW2029514348MaRDI QIDQ1944093

Zeev Nutov, Guy Kortsarz, Guy Even

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.12.010

zbMATH Keywords

approximation algorithmslaminar familytree augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (5)

A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius ⋮ Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs ⋮ Covering a laminar family by leaf to leaf links ⋮ Unnamed Item ⋮ A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius

Cites Work

• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Unnamed Item

This page was built for publication: A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\)