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 条
  • [31] Comparative Analysis of Vertex Cover Computation Algorithms for Varied Graphs
    Patel, Smit
    Kamath, Sowmya S.
    2014 INTERNATIONAL CONFERENCE ON COMMUNICATIONS AND SIGNAL PROCESSING (ICCSP), 2014,
  • [32] Hamiltonicity in vertex envelopes of plane cubic graphs
    Fleischner, Herbert
    Hobbs, Arthur M.
    Muzhevec, Michael Tapfuma
    DISCRETE MATHEMATICS, 2009, 309 (14) : 4793 - 4809
  • [33] PARTIAL VERTEX COVER AND BUDGETED MAXIMUM COVERAGE IN BIPARTITE GRAPHS
    Caskurlu, Bugra
    Mkrtchyan, Vahan
    Parekh, Ojas
    Subramani, K.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) : 2172 - 2184
  • [34] Vertex-edge domination in cubic graphs
    Ziemann, Radoslaw
    Zylinski, Pawel
    DISCRETE MATHEMATICS, 2020, 343 (11)
  • [35] The k-path vertex cover of rooted product graphs
    Jakovac, Marko
    DISCRETE APPLIED MATHEMATICS, 2015, 187 : 111 - 119
  • [36] Computational Analysis of different Vertex Cover Algorithms of Various Graphs
    Patel, Khushbu
    Patel, Jitali
    2017 INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTING AND CONTROL SYSTEMS (ICICCS), 2017, : 730 - 734
  • [37] Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
    Miao, Dongjing
    Li, Jianzhong
    Liu, Xianmin
    Gao, Hong
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015), 2015, 9486 : 395 - 408
  • [38] The k-path vertex cover in Cartesian product graphs and complete bipartite graphs
    Li, Zhao
    Zuo, Liancui
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 331 : 69 - 79
  • [39] Vertex Cover Problem-Revised Approximation Algorithm
    Shah, Kartik
    Reddy, Praveenkumar
    Selvakumar, R.
    ARTIFICIAL INTELLIGENCE AND EVOLUTIONARY ALGORITHMS IN ENGINEERING SYSTEMS, VOL 1, 2015, 324 : 9 - 16
  • [40] On the weighted k-path vertex cover problem
    Bresar, B.
    Krivos-Bellus, R.
    Semanisin, G.
    Sparl, P.
    DISCRETE APPLIED MATHEMATICS, 2014, 177 : 14 - 18
12345