The problem of finding a minimum weight k-vertex connected spanning subgraph in a graph G = (V, E) is considered. For k >= 2, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there exist k internally vertex-disjoint paths to every other vertex), we derive polynomial time algorithm for finding a ([k/2] + 1)-connected subgraph with a weight at most twice the optimum to the original problem. In particular, we obtain a 2-approximation algorithm for the case k = 3 of our problem. This improves the best previously known approximation ratio 3. The complexity of the algorithm is O(|V|~3|E|) = O(|V|~5).
展开▼
机译：考虑了在图G =（V，E）中找到最小权重k顶点连接的跨子图的问题。对于k> = 2，已知此问题是NP-难问题。结合包含最小k顶点连接的图和k向外连接图的属性（即，包含一个顶点的图，从该顶点到每个其他顶点都有k条内部不相交的路径），我们推导了多项式时间算法来查找一个（[k / 2] +1）连接的子图，其权重最多是原始问题的最佳权重的两倍。特别是，对于问题的k = 3，我们获得了一种2近似算法。这提高了先前已知的最佳近似比率3。算法的复杂度为O（| V |〜3 | E |）= O（| V |〜5）。
展开▼
