Bicriteria approximation for $k$-edge-connectivity

Zeev Nutov, Reut Cohen

In the $k$-Edge Connected Spanning Subgraph ($k$-ECSS) problem we are given a (multi-)graph $G=(V,E)$ with edge costs and an integer $k$, and seek a min-cost $k$-edge-connected spa…