Given a #kappa# vertex-connected graph with weighted edges, we study the problem of finding a minimum weight spanning subgraph which is #kappa# vertex-connected, for small values of #kappa#. The problem is known to be NP-hard for any #kappa#, even when edges have no weight. In this paepr we provide a 2 approximation algorithm for the cases #kappa#=2,3 and a 3 approximation algorithm for the case #kappa#=4. The best approximation factors present in literature are 2,3 +2/3 and 4+1/6, respectively.
展开▼
