A primal-dual approximation algorithm for the vertex cover P3 problem

被引：60

作者：

Tu, Jianhua ^{[1
]}

Zhou, Wenli ^{[2
]}

机构：

[1] Beijing Univ Chem Technol, Sch Sci, Beijing 100029, Peoples R China

[2] IBM Res China, Beijing 100193, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2011年 / 412卷 / 50期

关键词：

Combinatorial optimization; Approximation algorithm; Vertex cover P-n problem; The primal-dual method; UNDIRECTED GRAPHS; SET PROBLEM;

D O I：

10.1016/j.tcs.2011.09.013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce the vertex cover P-n (VCPn) problem, that is, the problem of finding a minimum weight set F subset of V such that the graph G[V - F] has no P-n, where P-n is a path with n vertices. The problem also has its application background. In this paper, we first show that the VCPn problem is NP-hard for any integer n >= 2. Then we restrict our attention to the VCP3 problem and give a 2-approximation algorithm using the primal-dual method. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：7044 / 7048

页数：5

共 50 条

[41] Extending the Primal-Dual 2-Approximation Algorithm Beyond Uncrossable Set Families [J].

Nutov, Zeev .

INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2024, 2024, 14679 :351-364

[42] On approximation of the vertex cover problem in hypergraphs [J].

Okun, Michael .

Discrete Optimization, 2005, 2 (01) :101-111

[43] Improved Approximation Algorithm for Vertex Cover Problem using Articulation Points [J].

Patel, Smit ;

Kamath, Sowmya S. .

2014 INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND NETWORKING TECHNOLOGIES (ICCCNT, 2014,

[44] A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties [J].

Liu, Xiaofei ;

Li, Weidong .

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019, 2019, 11640 :203-211

[45] Primal-dual approximation algorithms for integral flow and multicut in trees [J].

N. Garg ;

V. V. Vazirani ;

M. Yannakakis .

Algorithmica, 1997, 18 :3-20

[46] Primal-dual approximation algorithms for integral flow and multicut in trees [J].

Garg, N ;

Vazirani, VV ;

Yannakakis, M .

ALGORITHMICA, 1997, 18 (01) :3-20

[47] A PRIMAL-DUAL APPROXIMATION ALGORITHM FOR MIN-SUM SINGLE-MACHINE SCHEDULING PROBLEMS [J].

Cheung, Maurice ;

Mestre, Julian ;

Shmoys, David B. ;

Verschae, Jose .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (02) :825-838

[48] An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem [J].

Jian-hua Tu ;

Jun-feng Du ;

Feng-mei Yang .

Acta Mathematicae Applicatae Sinica, English Series, 2014, 30 :271-278

[49] An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem [J].

Jian-hua TU ;

Jun-feng DU ;

Feng-mei YANG .

Acta Mathematicae Applicatae Sinica, 2014, (02) :271-278

[50] An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem [J].

Tu, Jian-hua ;

Du, Jun-feng ;

Yang, Feng-mei .

ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2014, 30 (02) :271-278

← 1 2 3 4 5 →