A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Tài liệu tham khảo
G. Even, J. Feldman, G. Kortsarz, Z. Nutov, A 3/2-approximation for augmenting a connected graph into a two-connected graph, in: APPROX, 2001, pp. 90–101.
Even, 2009, A 1.8-approximation for augmenting edge-connectivity of a graph from 1 to 2, Transactions on Algorithms, 5
Nagamochi, 2003, An approximation for finding a smallest 2-edge connected subgraph containing a specified spanning tree, Discrete Applied Mathematics, 126, 83, 10.1016/S0166-218X(02)00218-4