Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem

DOI10.1007/11496915_31MaRDI QIDQ3596353zbMATH OpenOpenAlexFDO

Authors Prabhakar Gubbala, Balaji Raghavachari

Publication date 30 August 2007

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11496915_31

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2079404
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity

Cited in

(10)

• A 2-approximation algorithm for the network substitution problem
• A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
• Approximating the minimum strongly connected subgraph via a matching lower bound
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• scientific article; zbMATH DE number 1187147 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
• A 4/3 approximation for 2-vertex-connectivity

This page was built for publication: Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem

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