scientific article; zbMATH DE number 1187147

zbMATH Open0909.90262MaRDI QIDQ3840352FDOQ3840352

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

Publication date: 10 August 1998

Title of this publication is not available (Why is that?)

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

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)

Cited In (16)

• Minimum 2-edge connected spanning subgraph of certain graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Title not available (Why is that?)
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Approximating minimum size \{1,2\}-connected networks
• Finding 2-edge connected spanning subgraphs.
• Title not available (Why is that?)
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• Title not available (Why is that?)
• 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
• Approximating minimum-cost connected \(T\)-joins

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)