Faster approximation algorithms for weighted triconnectivity augmentation problems

被引：4

作者：

Nutov, Z ^{[1
]}

Penn, M ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

来源：

OPERATIONS RESEARCH LETTERS | 1997年 / 21卷 / 05期

关键词：

graph; vertex connectivity; augmentation problem; approximation algorithm;

D O I：

10.1016/S0167-6377(97)00045-X

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The problem of finding a minimum-weight augmenting edge-set to make a graph 3-vertex connected is considered. This problem is known to be NP-complete. We present a new 3-approximation algorithm for making an arbitrary graph 3-vertex connected. Our algorithm is simpler and faster than the previously known 3-approximation algorithm by a factor of O(n(2)), where n is the number of vertices of the graph. We also consider the problem of increasing the vert ex-connectivity of a 2-connected, graph from 2 to 3. (C) 1997 Elsevier Science B.V. All rights reserved.

引用

页码：219 / 223

页数：5

共 16 条

[1]

Eswaran K. P., 1976, SIAM Journal on Computing, V5, P653, DOI 10.1137/0205044

[2] AN APPLICATION OF SUBMODULAR FLOWS [J].

FRANK, A ;

TARDOS, E .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1989, 114 :329-348

[3]

FRANK A, 1994, MATH PROGRAMMING STA, P34

[4] APPROXIMATION ALGORITHMS FOR SEVERAL GRAPH AUGMENTATION PROBLEMS [J].

FREDERICKSON, GN ;

JAJA, J .

SIAM JOURNAL ON COMPUTING, 1981, 10 (02) :270-283

[5]

GABOW HN, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P202

[6]

GROTSCHEL M, 1993, HDB OPERATIONS RES M, V7

[7]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P135, DOI 10.1137/0202012

[8]

HSU T, 1994, UNPUB RAMACHANDRAN 2

[9]

HSU T, 1994, UNPUB RAMACHANDRAN 1

[10] ON THE OPTIMAL VERTEX-CONNECTIVITY AUGMENTATION [J].

JORDAN, T .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :8-20

← 1 2 →