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 条
  • [1] A factor 2 approximation algorithm for the vertex cover P3 problem
    Tu, Jianhua
    Zhou, Wenli
    INFORMATION PROCESSING LETTERS, 2011, 111 (14) : 683 - 686
  • [2] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
    Liu, Xiaofei
    Li, Weidong
    Yang, Jinhua
    FRONTIERS OF COMPUTER SCIENCE, 2023, 17 (03)
  • [3] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
    Xiaofei LIU
    Weidong LI
    Jinhua YANG
    Frontiers of Computer Science, 2023, 17 (03) : 128 - 135
  • [4] The vertex cover P3 problem in cubic graphs
    Tu, Jianhua
    Yang, Fengmei
    INFORMATION PROCESSING LETTERS, 2013, 113 (13) : 481 - 485
  • [5] A primal-dual algorithm for the minimum power partial cover problem
    Menghong Li
    Yingli Ran
    Zhao Zhang
    Journal of Combinatorial Optimization, 2022, 44 : 1913 - 1923
  • [6] A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem
    Liu, Xiaofei
    Li, Weidong
    Xie, Runtao
    OPTIMIZATION LETTERS, 2022, 16 (08) : 2373 - 2385
  • [7] A primal-dual algorithm for the minimum power partial cover problem
    Li, Menghong
    Ran, Yingli
    Zhang, Zhao
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (03) : 1913 - 1923
  • [8] A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem
    Xiaofei Liu
    Weidong Li
    Runtao Xie
    Optimization Letters, 2022, 16 : 2373 - 2385
  • [9] Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties
    Xu, Dachuan
    Wang, Fengmin
    Du, Donglei
    Wu, Chenchen
    COMPUTING AND COMBINATORICS, COCOON 2014, 2014, 8591 : 336 - 345
  • [10] A fixed-parameter algorithm for the vertex cover P3 problem
    Tu, Jianhua
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 96 - 99
12345