A new bound for the 2-edge connected subgraph problem

DOI10.1007/3-540-69346-7_9MaRDI QIDQ3840351zbMATH OpenFDO

Authors Robert D. Carr, R. Ravi

Publication date 10 August 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://www.osti.gov/biblio/671991

zbMATH Keywords

2-edge connected subgraph problemlinear programming relaxationsalesman problem

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• An improved approximation algorithm for minimum size 2-edge connected spanning subgraphs
• Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• The 2-edge-connected subgraph polyhedron

Cited in

(20)

• Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Shorter tours and longer detours: uniform covers and a bit beyond
• The salesman's improved tours for fundamental classes
• The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• The 2-edge-connected subgraph polyhedron
• Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• Towards improving Christofides algorithm for half-integer TSP
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• On the bidirected cut relaxation for Steiner forest
• A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP

This page was built for publication: A new bound for the 2-edge connected subgraph problem

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