IMPROVED APPROXIMATION ALGORITHMS FOR WEIGHTED 2-VERTEX AND 3-VERTEX CONNECTIVITY AUGMENTATION PROBLEMS

The problem of finding a minimum augmenting edge-set to make a graph k -vertex connected is considered. This problem is denoted as the minimu m k-augmentation problem. For weighted graphs, the minimum k-augmentat ion problem is NP-complete. Our main result is an approximation algori thm with a performance ratio of 3 for solving the minimum 3-augmentati on problem. This improves the best previously known performance guaran tee of 11/3. We also have the following marginal result: an approximat ion algorithm for the minimum 2-augmentation problem that achieves a f actor of 2, and thus improves the previously known factor of 2 + (1/n) , with n as the number of vertices in the graph. (C) 1997 Academic Pre ss.