Edge-connectivity augmentation problems (Q1091147)

We give a characterization on the minimum number of edges to be added so as to k-edge-connect a graph. We also show that such a minimum edge set can be determined in \({\mathcal O}(kL| V|^ 4(k| V| +| E|))\) time for any graph \(G=(V,E)\) and any fixed \(k\geq 2\), where \(L=\min \{k,| V| \}\).