Better Algorithms for Minimum Weight Vertex-Connectivity Problems

Abstract

Given a k vertex connected graph with weighted edges, we study the problem of nding a minimum weight spanning subgraph which is k vertex-connected, for k = 2; 3; 4. The problem is known to be NP-hard for any k, even when edges have no weight, and various approximation algorithms have been proposed. The best approximation factors that have been obtained are 2; 3 and 25 6 , for the cases k = 2; 3; 4, respectively. In this paper we provide an 2 approximation algorithm for the case k = 3 and a 3 approximation algorithm for the case k = 4, thus improving on the algorithms found in literature. Moreover, we give a new algorithm for the case k = 2 that obtains an approximation factor 2.

Topics

    0 Figures and Tables

      Download Full PDF Version (Non-Commercial Use)