Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331866 | Information Processing Letters | 2015 | 4 Pages |
Abstract
A subset F of vertices of a graph G is called a vertex cover Pt set if every path of order t in G contains at least one vertex from F. Denote by Ït(G) the minimum cardinality of a vertex cover Pt set in G. The vertex cover Pt (VCPt) problem is to find a minimum vertex cover Pt set. The VCPt problem is NP-hard for any integer tâ¥2. In this paper, we restrict our attention to the VCP3 problem and present a fixed-parameter algorithm with runtime O(2kk3.376+n4m) for the VCP3 problem. Here, n denotes the number of vertices, m denotes the number of the edges, k denotes the size of the vertex cover P3 set searched for.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jianhua Tu,