Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem

DOI10.1016/j.endm.2015.07.071zbMath1347.05107arXiv1512.08070OpenAlexW2200051489MaRDI QIDQ324874

Sylvia Boyd, Philippe Legault

Publication date: 17 October 2016

Full work available at URL: https://arxiv.org/abs/1512.08070

zbMATH Keywords

approximation algorithmintegrality gapminimum cost 2-edge connected subgraph problem

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem