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

被引：58
作者：
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] AN EFFICIENT POLYNOMIAL TIME APPROXIMATION SCHEME FOR THE VERTEX COVER P3 PROBLEM ON PLANAR GRAPHS
    Tu, Jianhua
    Shi, Yongtang
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) : 55 - 65
  • [22] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
    Xing Wang
    Dachuan Xu
    Xinyuan Zhao
    Frontiers of Mathematics in China, 2011, 6 : 957 - 964
  • [23] A primal-dual approximation algorithm for stochastic facility location problem with service installation costs
    Wang, Xing
    Xu, Dachuan
    Zhao, Xinyuan
    FRONTIERS OF MATHEMATICS IN CHINA, 2011, 6 (05) : 957 - 964
  • [24] A Primal-Dual Approximation Algorithm for the k-Level Stochastic Facility Location Problem
    Wang, Zhen
    Du, Donglei
    Xu, Dachuan
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2010, 6124 : 253 - +
  • [25] An Approximation Algorithm for the Minimum Vertex Cover Problem
    Chen, Jingrong
    Kou, Lei
    Cui, Xiaochuan
    GREEN INTELLIGENT TRANSPORTATION SYSTEM AND SAFETY, 2016, 138 : 180 - 185
  • [26] A New Approximation Algorithm for Vertex Cover Problem
    Dahiya, Sonika
    2013 INTERNATIONAL CONFERENCE ON MACHINE INTELLIGENCE AND RESEARCH ADVANCEMENT (ICMIRA 2013), 2013, : 472 - 478
  • [27] A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
    Chudak, FA
    Goemans, MX
    Hochbaum, DS
    Williamson, DP
    OPERATIONS RESEARCH LETTERS, 1998, 22 (4-5) : 111 - 118
  • [28] A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem
    Zhang, Wenjie
    Tu, Jianhua
    Wu, Lidong
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 349 : 359 - 366
  • [29] A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs
    Li, Yuchao
    Tu, Jianhua
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2014, 91 (10) : 2103 - 2108
  • [30] A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP
    Viet Hung Nguyen
    Journal of Combinatorial Optimization, 2013, 25 : 265 - 278
12345