(2-2/|V|)-approximation algorithms for several graph connectivity related problems

摘要

First, for the problems of finding a minimum weight strongly connected spanning subgraph and a minimum weight k-edge-connected spanning subgraph of a given edge-weighted directed or undirected graph, respectively, we propose (2 - (2/|V|))-approximation algorithms. Next, for the problem of finding a minimum weight augmenting edge-set to increase the edge-connectivity of a given graph by one, we propose a (2 - (2/|L|))-approximation algorithm, where L is the set of leaves of a certain tree constructed from the graph. Each of the proposed algorithms repeats execution of the existing 2-approximation algorithm, and then selects the best solution among those obtained, improving the previously known performance ratio by (2/|V|) or (2/|L|).