A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem

DOI10.1006/JAGM.1998.0931MaRDI QIDQ4216147zbMATH OpenOpenAlexFDO

Authors Cristina G. Fernandes

Publication date 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1998.0931

zbMATH Keywords

\(k\)-edge-connected spanning subgraph problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
• scientific article; zbMATH DE number 2079371
• scientific article; zbMATH DE number 1187147
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching

Cited in

(18)

• On k-connectivity problems with sharpened triangle inequality
• Finding 2-edge connected spanning subgraphs.
• Approximating minimum size \{1,2\}-connected networks
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Network flow spanners
• scientific article; zbMATH DE number 1187147 (Why is no real title available?)
• scientific article; zbMATH DE number 2079371 (Why is no real title available?)
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
• An Improved Analysis for Approximating the Smallest k-Edge Connected Spanning Subgraph of a Multigraph
• Special edges, and approximating the smallest directed k-edge connected spanning subgraph
• An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• Bicriteria approximation for k-edge-connectivity
• Fault-tolerant matroid bases
• Approximation schemes for planar graph connectivity problems

This page was built for publication: A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem

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