A (1+ 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius

DOI10.1016/J.TCS.2013.04.004MaRDI QIDQ388116zbMATH OpenOpenAlexFDO

Authors Nachshon Cohen, Zeev Nutov

Publication date 19 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.04.004

zbMATH Keywords

approximation algorithmsedge-connectivitylaminar familylocal replacementtree augmentation

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• A \((1 + \ln 2)\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• scientific article; zbMATH DE number 1979495
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Minimum augmentation of a tree to a K-edge-connected graph
• Algorithms for radius-optimally augmenting trees in a metric space
• Algorithms for radius-optimally augmenting trees in a metric space
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Improved approximation algorithms for min-cost connectivity augmentation problems

Cites work

• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Covering a laminar family by leaf to leaf links
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems

Cited in

(22)

• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• Covering a laminar family by leaf to leaf links
• On the tree augmentation problem
• Approximating Steiner trees and forests with minimum number of Steiner points
• Approximating Steiner trees and forests with minimum number of Steiner points
• Approximation algorithms for vertex-connectivity augmentation on the cycle
• 2-node-connectivity network design
• Node connectivity augmentation via iterative randomized rounding
• A \((1 + \ln 2)\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Approximation algorithms for node and element connectivity augmentation problems
• A simple LP-based approximation algorithm for the matching augmentation problem
• A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
• LP-relaxations for tree augmentation
• 2-node-connectivity network design
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• On the cycle augmentation problem: hardness and approximation algorithms
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On small-depth tree augmentations

This page was built for publication: A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388116)