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 条

[21] A Primal-Dual Approximation Algorithm for the k-Level Stochastic Facility Location Problem [J].

Wang, Zhen ;

Du, Donglei ;

Xu, Dachuan .

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2010, 6124 :253-+

[22] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs [J].

Wang, Xing ;

Xu, Dachuan ;

Zhao, Xinyuan .

FRONTIERS OF MATHEMATICS IN CHINA, 2011, 6 (05) :957-964

[23] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs [J].

Xing Wang ;

Dachuan Xu ;

Xinyuan Zhao .

Frontiers of Mathematics in China, 2011, 6 :957-964

[24] An Approximation Algorithm for the Minimum Vertex Cover Problem [J].

Chen, Jingrong ;

Kou, Lei ;

Cui, Xiaochuan .

GREEN INTELLIGENT TRANSPORTATION SYSTEM AND SAFETY, 2016, 138 :180-185

[25] A New Approximation Algorithm for Vertex Cover Problem [J].

Dahiya, Sonika .

2013 INTERNATIONAL CONFERENCE ON MACHINE INTELLIGENCE AND RESEARCH ADVANCEMENT (ICMIRA 2013), 2013, :472-478

[26] A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs [J].

Chudak, FA ;

Goemans, MX ;

Hochbaum, DS ;

Williamson, DP .

OPERATIONS RESEARCH LETTERS, 1998, 22 (4-5) :111-118

[27] A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem [J].

Zhang, Wenjie ;

Tu, Jianhua ;

Wu, Lidong .

APPLIED MATHEMATICS AND COMPUTATION, 2019, 349 :359-366

[28] A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs [J].

Li, Yuchao ;

Tu, Jianhua .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2014, 91 (10) :2103-2108

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

Viet Hung Nguyen .

Journal of Combinatorial Optimization, 2013, 25 :265-278

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

Viet Hung Nguyen .

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

← 1 2 3 4 5 →