A 4/3-approximation algorithm for minimum 3-edge-connectivity

被引：0

作者：

Gubbala, Prabhakar ^{[1
]}

Raghavachari, Balaji ^{[2
]}

机构：

[1] Microsoft Corp, Redmond, WA 98052 USA

[2] Univ Texas Dallas, Comp Sci Dept, Richardson, TX 75083 USA

来源：

ALGORITHMS AND DATA STRUCTURES, PROCEEDINGS | 2007年 / 4619卷

关键词：

approximation algorithms; graph and network algorithms; connectivity; combinatorial optimization;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The minimum cardinality 3-edge-connected spanning sub-graph problem is considered. An approximation algorithm with a performance ratio of 4/3 approximate to 1.33 is presented. This improves the previous best ratio of 3/2 for the problem. The algorithm also works on multigraphs and guarantees the same approximation ratio.

引用

页码：39 / +

页数：3

共 9 条

[1] Approximating minimum-size k-connected spanning subgraphs via matching
Cheriyan, J
Thurimella, R
[J]. SIAM JOURNAL ON COMPUTING, 2000, 30 (02) : 528 - 560
[2] Gabow HN, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P562
[3] An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph
Gabow, HN
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) : 41 - 70
[4] Gubbala P, 2005, LECT NOTES COMPUT SC, V3509, P422
[5] Jothi R, 2003, SIAM PROC S, P725
[6] BICONNECTIVITY APPROXIMATIONS AND GRAPH CARVINGS
KHULLER, S
VISHKIN, U
[J]. JOURNAL OF THE ACM, 1994, 41 (02) : 214 - 235
[7] Khuller Samir, 1997, APPROXIMATION ALGORI, P236
[8] KORTSARZ G, 2007, HDB APPROXIMATION AL, V10, pCH58
[9] Vempala S., 2000, Approximation Algorithms for Combinatorial Optimization. Third International Workshop, APPROX 2000. Proceedings (Lecture Notes in Computer Science Vol.1913), P262

← 1 →