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 条
  • [21] Computational complexity of minimum P4 vertex cover problem for regular and K1,4-free graphs
    Devi, N. Safina
    Mane, Aniket C.
    Mishra, Sounaka
    DISCRETE APPLIED MATHEMATICS, 2015, 184 : 114 - 121
  • [22] Efficient algorithm for the vertex cover Pk problem on cacti
    Tu, Jianhua
    APPLIED MATHEMATICS AND COMPUTATION, 2017, 311 : 217 - 222
  • [23] On approximating minimum vertex cover for graphs with perfect matching
    Chen, JN
    Kanj, IA
    THEORETICAL COMPUTER SCIENCE, 2005, 337 (1-3) : 305 - 318
  • [24] Path Vertex Cover Number of Some Product Graphs
    Liu, Yan
    Deng, Xingchao
    JOURNAL OF INTERCONNECTION NETWORKS, 2024,
  • [25] Approximation algorithms for the partition vertex cover problem
    Bera, Suman K.
    Gupta, Shalmoli
    Kumar, Amit
    Roy, Sambuddha
    THEORETICAL COMPUTER SCIENCE, 2014, 555 : 2 - 8
  • [26] 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
  • [27] A Better Approximation Ratio for the Vertex Cover Problem
    Karakostas, George
    ACM TRANSACTIONS ON ALGORITHMS, 2009, 5 (04)
  • [28] NMVSA Greedy Solution for Vertex Cover Problem
    Eshtay, Mohammed
    Sliet, Azzam
    Sharieh, Ahmad
    INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 2016, 7 (03) : 60 - 64
  • [29] Some Results on Incremental Vertex Cover Problem
    Dai, Wenqiang
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2010, 6124 : 112 - 118
  • [30] A New Approximation Algorithm for Vertex Cover Problem
    Dahiya, Sonika
    2013 INTERNATIONAL CONFERENCE ON MACHINE INTELLIGENCE AND RESEARCH ADVANCEMENT (ICMIRA 2013), 2013, : 472 - 478
12345