ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY
Alessandro Ferrante, Mimmo Parente · International Journal of Foundations of Computer Science · 2004
Given a graph with the edge costs satisfying the β-sharpened triangle inequality: cost(u,v)≤β(cost(u,x)+cost(x,v)), for l/2≤β<1, we study the NP-hard problem of finding a minimum cost spanning subgraph which is k-vertex-connected, k≥2. We analyze an approximation quadratic-time algorithm whose performance ratio is [Formula: see text]. 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.