A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Information Processing Letters - Tập 111 - Trang 296-300 - 2011
Guy Even1, Guy Kortsarz2, Zeev Nutov3
1Tel-Aviv University, Israel
2Rutgers University, Camden, United States
3The Open University of Israel, Israel

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