Article ID: | iaor2002902 |
Country: | Netherlands |
Volume: | 21 |
Issue: | 5 |
Start Page Number: | 219 |
End Page Number: | 223 |
Publication Date: | Dec 1997 |
Journal: | Operations Research Letters |
Authors: | Penn Michal, Nutov Zeev |
The problem of finding a minimum-weight augmenting edge-set to make a graph 3-vertex connected is considered. This problem is known to be NP-complete. We present a new 3-approximation algorithm for making an arbitrary graph 3-vertex connected. Our algorithm is simpler and faster than the previously known 3-approximation algorithm by a factor of O(