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 条
  • [41] A Survey on the k-Path Vertex Cover Problem
    Tu, Jianhua
    AXIOMS, 2022, 11 (05)
  • [42] An Improved Memetic Algorithm for the Partial Vertex Cover Problem
    Zhou, Yupeng
    Qiu, Changze
    Wang, Yiyuan
    Fan, Mingjie
    Yin, Minghao
    IEEE ACCESS, 2019, 7 : 17389 - 17402
  • [43] Complexity and approximation results for the connected vertex cover problem
    Escoffier, Bruno
    Gourves, Laurent
    Monnot, Jerome
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2007, 4769 : 202 - +
  • [44] An edge-reduction algorithm for the vertex cover problem
    Han, Qiaoming
    Punnen, Abraham P.
    Ye, Yinyu
    OPERATIONS RESEARCH LETTERS, 2009, 37 (03) : 181 - 186
  • [45] Mean analysis of an online algorithm for the vertex cover problem
    Birmele, Etienne
    Delbot, Francois
    Laforest, Christian
    INFORMATION PROCESSING LETTERS, 2009, 109 (09) : 436 - 439
  • [46] On approximation of the vertex cover problem in hypergraphs
    Okun, Michael
    Discrete Optimization, 2005, 2 (01) : 101 - 111
  • [47] Strong Rainbow Vertex-Connection of Cubic Graphs
    Arputhamary, I. Annammal
    Mercy, M. Helda
    PROCEEDINGS OF 2015 IEEE 9TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS AND CONTROL (ISCO), 2015,
  • [48] Cubic vertex-transitive graphs of girth six
    Potacnik, Primoz
    Vidali, Janos
    DISCRETE MATHEMATICS, 2022, 345 (03)
  • [49] Approximation Algorithms for the L-Distance Vertex Cover Problem
    Chen, Qiaoyun
    Zhao, Liang
    2012 THIRD INTERNATIONAL CONFERENCE ON THEORETICAL AND MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE (ICTMF 2012), 2013, 38 : 100 - 104
  • [50] Complexity of the Maximum k-Path Vertex Cover Problem
    Miyano, Eiji
    Saitoh, Toshiki
    Uehara, Ryuhei
    Yagita, Tsuyoshi
    van der Zanden, Tom C.
    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2018, 2018, 10755 : 240 - 251
12345