The vertex cover P3 problem in cubic graphs

被引：33
作者：
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
相关论文
共 11 条
[1]   A 2-approximation algorithm for the undirected feedback vertex set problem [J].
Bafna, V ;
Berman, P ;
Fujito, T .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297
[2]   A LINEAR-TIME APPROXIMATION ALGORITHM FOR THE WEIGHTED VERTEX COVER PROBLEM [J].
BARYEHUDA, R ;
EVEN, S .
JOURNAL OF ALGORITHMS, 1981, 2 (02) :198-203
[3]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[4]   On the vertex k-path cover [J].
Bresar, Bostjan ;
Jakovac, Marko ;
Katrenic, Jan ;
Semanisin, Gabriel ;
Taranenko, Andrej .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) :1943-1949
[5]   Minimum k-path vertex cover [J].
Bresar, Bostjan ;
Kardos, Frantisek ;
Katrenic, Jan ;
Semanisin, Gabriel .
DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1189-1195
[6]   A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs [J].
Chudak, FA ;
Goemans, MX ;
Hochbaum, DS ;
Williamson, DP .
OPERATIONS RESEARCH LETTERS, 1998, 22 (4-5) :111-118
[7]  
Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
[8]   On computing the minimum 3-path vertex cover and dissociation number of graphs [J].
Kardos, Frantisek ;
Katrenic, Jan ;
Schiermeyer, Ingo .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) :7009-7017
[9]   Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs [J].
Liang, Zuosong ;
Shan, Erfang .
INFORMATION PROCESSING LETTERS, 2011, 111 (23-24) :1104-1107
[10]   A primal-dual approximation algorithm for the vertex cover P3 problem [J].
Tu, Jianhua ;
Zhou, Wenli .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) :7044-7048
12