The vertex cover P3 problem in cubic graphs

被引：32
|
作者：
Tu, Jianhua [1 ]
Yang, Fengmei [1 ]
机构：
[1] Beijing Univ Chem Technol, Sch Sci, Beijing 100029, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 13期
基金：
中国国家自然科学基金;
关键词：
Combinatorial optimization; Vertex cover P-3 problem; Approximation algorithm; Cubic graph; APPROXIMATION ALGORITHM; SET PROBLEM;
D O I：
10.1016/j.ipl.2013.04.002
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A subset F of vertices of a graph G is called a vertex cover P-k set if every path of order k in G contains at least one vertex from F. Denote by psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The vertex cover P-k (VCPk) problem is to find a minimum vertex cover P-k set. In this paper, we restrict our attention to the VCP3 problem in cubic graphs. This paper proves that the VCP3 problem is NP-hard for cubic planar graphs of girth 3. Further we give sharp lower and upper bounds on psi(3)(G) for cubic graphs and propose a 1.57-approximation algorithm for the VCP3 problem in cubic graphs. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：481 / 485
页数：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 vertex cover P3 problem
    Tu, Jianhua
    Zhou, Wenli
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) : 7044 - 7048
  • [3] 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
  • [4] On the vertex cover P3 problem parameterized by treewidth
    Tu, Jianhua
    Wu, Lidong
    Yuan, Jing
    Cui, Lei
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) : 414 - 425
  • [5] An improved algorithm for the vertex cover P3 problem on graphs of bounded treewidth
    Bai, Zongwen
    Tu, Jianhua
    Shi, Yongtang
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2019, 21 (04)
  • [6] A fixed-parameter algorithm for the vertex cover P3 problem
    Tu, Jianhua
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 96 - 99
  • [7] 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
  • [8] Fixed-parameter algorithms for vertex cover P3
    Chang, Maw-Shang
    Chen, Li-Hsuan
    Hung, Ling-Ju
    Rossmanith, Peter
    Su, Ping-Chen
    DISCRETE OPTIMIZATION, 2016, 19 : 12 - 22
  • [9] 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
  • [10] A PTAS for minimum weighted connected vertex cover P3 problem in 3-dimensional wireless sensor networks
    Wang, Limin
    Du, Wenxue
    Zhang, Zhao
    Zhang, Xiaoyan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (01) : 106 - 122
12345