scientific article; zbMATH DE number 1187147

MaRDI QIDQ3840352zbMATHFDO

Authors András Sebö, Zoltán Szigeti, Joseph Cheriyan

Publication date 10 August 1998

zbMATH Keywords

approximation guarantee2-edge connected spanning subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
• An improved approximation algorithm for the minimum k -edge connected multi-subgraph problem
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Publication:4938657
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem

Cited in

(18)

• Minimum 2-edge connected spanning subgraph of certain graphs
• scientific article; zbMATH DE number 1688381 (Why is no real title available?)
• scientific article; zbMATH DE number 1405676 (Why is no real title available?)
• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• Approximating minimum-cost connected \(T\)-joins
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• Approximating minimum size \{1,2\}-connected networks
• Finding 2-edge connected spanning subgraphs.

This page was built for publication:

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