Finding 2-edge connected spanning subgraphs

被引：5

作者：

Huh, WT ^{[1
]}

机构：

[1] Columbia Univ, Ind Engn & Operat Res Dept, New York, NY 10027 USA

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 03期

关键词：

graph; 2-edge connectivity; approximation algorithm; linear programming;

D O I：

10.1016/j.orl.2003.08.006

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V, E) finds a 2-ECSS of size at most \V\ +(\E\ - \V\)/(r- 1). For r-regular, r-edge connected input graphs for r = 3, 4, 5 and 6, this gives approximation guarantees of 5/4, 4/3, 11/8 and 7/5, respectively. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：212 / 216

页数：5

共 7 条

[1]

[Anonymous], 1979, GRAPH THEORY INTRO C, DOI DOI 10.1007/978-1-4612-9967-7

[2]

Cheriyan J, 1998, LECT NOTES COMPUT SC, V1412, P126

[3]

GARG N, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P103

[4] BICONNECTIVITY APPROXIMATIONS AND GRAPH CARVINGS [J].

KHULLER, S ;

VISHKIN, U .

JOURNAL OF THE ACM, 1994, 41 (02) :214-235

[5]

KRYSTA P, 2001, P 18 INT S THEOR ASP

[6]

VEMPALA S, 2000, P 3 WORKSH APPR SAAR

[7] Non-separable and planar graphs [J].

Whitney, Hassler .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1932, 34 (1-4) :339-362

← 1 →