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

DOI10.1006/jagm.1998.0931zbMath0919.68096OpenAlexW2037686175MaRDI QIDQ4216147

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)

Related Items (6)

On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY ⋮ Approximating the smallest k -edge connected spanning subgraph by LP-rounding ⋮ Network flow spanners ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Approximating minimum size \{1,2\}-connected networks

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