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 条

[31] A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP [J].

Viet Hung Nguyen .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (02) :265-278

[32] Vertex Cover Problem-Revised Approximation Algorithm [J].

Shah, Kartik ;

Reddy, Praveenkumar ;

Selvakumar, R. .

ARTIFICIAL INTELLIGENCE AND EVOLUTIONARY ALGORITHMS IN ENGINEERING SYSTEMS, VOL 1, 2015, 324 :9-16

[33] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

El Ouali, Mourad ;

Fohlin, Helena ;

Srivastav, Anand .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (02) :846-864

[34] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

Mourad El Ouali ;

Helena Fohlin ;

Anand Srivastav .

Journal of Combinatorial Optimization, 2016, 31 :846-864

[35] A Primal-Dual Algorithm for Euclidean k-Means Problem with Penalties [J].

Ren, Chunying ;

Xu, Dachuan ;

Du, Donglei ;

Li, Min .

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2020, 2020, 12337 :377-389

[36] Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach [J].

Wu, Chenchen ;

Du, Donglei ;

Xu, Dachuan .

THEORETICAL COMPUTER SCIENCE, 2015, 562 :213-226

[37] A Local 2-Approximation Algorithm for the Vertex Cover Problem [J].

Astrand, Matti ;

Floreen, Patrik ;

Polishchuk, Valentin ;

Rybicki, Joel ;

Suomela, Jukka ;

Uitto, Jara .

DISTRIBUTED COMPUTING, PROCEEDINGS, 2009, 5805 :191-205

[38] PRIMAL-DUAL APPROXIMATION ALGORITHMS FOR SUBMODULAR COST SET COVER PROBLEMS WITH LINEAR/SUBMODULAR PENALTIES [J].

Wang, Fengmin ;

Xu, Dachuan ;

Du, Donglei ;

Wu, Chenchen .

NUMERICAL ALGEBRA CONTROL AND OPTIMIZATION, 2015, 5 (02) :91-100

[39] Fixed-parameter algorithms for vertex cover P3 [J].

Chang, Maw-Shang ;

Chen, Li-Hsuan ;

Hung, Ling-Ju ;

Rossmanith, Peter ;

Su, Ping-Chen .

DISCRETE OPTIMIZATION, 2016, 19 :12-22

[40] A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem [J].

Han L. ;

Xu D.-C. ;

Du D.-L. ;

Wu C.-C. .

Journal of the Operations Research Society of China, 2017, 5 (2) :219-231

← 1 2 3 4 5 →