On the vertex-connectivity problem for graphs with sharpened triangle inequality
Given a graph with the edge costs satisfying the beta-sharpened triangle inequality: cost(u, v) less than or equal to beta(cost(u, x) + cost(x, v)), for 1/2 less than or equal to beta < 1, we study the NP-hard problem of finding a minimum cost spanning subgraph which is k-vertex-connected, k greater than or equal to 2. We analyze an approximation quadratic-time algorithm whose performance ratio is beta/1-beta. The main motivation of this study is to provide an algorithm with a good performance ratio and a practical worst case running time for significative subclasses of the metric Travelling Salesman Problem and the naturally related to it connectivity problems.
triangle inequality approximation algorithms apx-hardness vertex/edge connectivity