A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem

被引：3

作者：

Civril, A. ^{[1
]}

机构：

[1] Atlas Univ, Comp Engineenng Dept, TR-34408 Istanbul, Turkey

来源：

THEORETICAL COMPUTER SCIENCE | 2023年 / 943卷

关键词：

Minimum 2-edge-connected spanning; subgraph problem; Approximation algorithms; Combinatorial optimization; 5/4-APPROXIMATION; TSP;

D O I：

10.1016/j.tcs.2022.12.013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is 43 , which matches the current best ratio. The approximation ratio of the algorithm is s on subcubic graphs, which is an improvement upon the previous best ratio of 54. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches.(c) 2022 Elsevier B.V. All rights reserved.

引用

页码：121 / 130

页数：10

共 9 条

[1] A 5/4-approximation for subcubic 2EC using circulations and obliged edges [J].

Boyd, Sylvia ;

Fu, Yao ;

Sun, Yu .

DISCRETE APPLIED MATHEMATICS, 2016, 209 :48-58

[2] Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph [J].

Cheriyan, J ;

Sebo, A ;

Szigeti, Z .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, 14 (02) :170-180

[3]

Csaba B, 2002, SIAM PROC S, P74

[4] A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem [J].

Hunkenschroeder, Christoph ;

Vempala, Santosh ;

Vetta, Adrian .

ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (04)

[5]

Jothi R, 2003, SIAM PROC S, P725

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

KHULLER, S ;

VISHKIN, U .

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

[7]

Krysta P., 2001, STACS 2001. 18th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings (Lecture Notes in Computer Science Vol.2010), P431

[8] Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs [J].

Sebo, Andras ;

Vygen, Jens .

COMBINATORICA, 2014, 34 (05) :597-629

[9]

Vempala S., 2000, Approximation Algorithms for Combinatorial Optimization. Third International Workshop, APPROX 2000. Proceedings (Lecture Notes in Computer Science Vol.1913), P262

← 1 →