An approximation algorithm for the minimum-cost k-vertex connected subgraph

被引：52

作者：

Cheriyan, J ^{[1
]}

Vempala, S

Vetta, A

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] MIT, Dept Math, Cambridge, MA 02139 USA

[3] McGill Univ, Dept Comp Sci, Montreal, PQ H3A 2A7, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2003年 / 32卷 / 04期

关键词：

approximation algorithm; l-critically; k-connected graph; linear programming relaxation; network design; k-outconnected graph; vertex connectivity;

D O I：

10.1137/S0097539701392287

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k(2). The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.

引用

页码：1050 / 1055

页数：6

共 16 条

[1]

A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph [J].