An Approximation Algorithm for Minimum 2-edge-connectivity
Yi Liu · Mathematica Applicata · 2007
In this paper,we present a new efficient approximation algorithm for the problem of finding the minimum(i.e.least number of edges)2-edge-connected spanning subgraph of a given undirected graph.The algorithm introduces the idea of removing edges.It is not by means of spanning-tree,but to break up the original graph,then add vertexes and delete edges to get a 2-edge connected spanning subgraph.