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

共 13 条

[1]

[Anonymous], 2001, Approximation algorithms

[2] A 2-approximation algorithm for the undirected feedback vertex set problem [J].

Bafna, V ;

Berman, P ;

Fujito, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297

[3] A LINEAR-TIME APPROXIMATION ALGORITHM FOR THE WEIGHTED VERTEX COVER PROBLEM [J].

BARYEHUDA, R ;

EVEN, S .

JOURNAL OF ALGORITHMS, 1981, 2 (02) :198-203

[4]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[5]

Bresar B., 2010, MINIMUM K PATH UNPUB

[6] 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

[7]

Dinur I, 2002, ANN IEEE SYMP FOUND, P33, DOI 10.1109/SFCS.2002.1181880

[8] Approximating minimum subset feedback sets in undirected graphs with applications [J].

Even, G ;

Naor, JS ;

Schieber, B ;

Zosin, L .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (02) :255-267

[9]

Goemans M.X., 1996, APPROXIMATION ALGORI

[10] Primal-dual approximation algorithms for feedback problems in planar graphs [J].

Goemans, MX ;

Williamson, DP .

COMBINATORICA, 1998, 18 (01) :37-59

← 1 2 →