Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking
We introduce the vertex cover P n (VCP n ) problem, that is, the problem of finding a minimum weight set F⊂V such that the graph G[V-F] has no P n , where P n is a path with n vertices. The problem also has its application background. In this paper, we first show that the VCP n problem is NP-hard for any integer n≥2. Then we restrict our attention to the VC P3 problem and give a 2-approximation algorithm using the primal-dual method. © 2011 Elsevier B.V. All rights reserved.
Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking
Preeti Malakar, Thomas George, et al.
SC 2012
Liqun Chen, Matthias Enzmann, et al.
FC 2005
Daniel M. Bikel, Vittorio Castelli
ACL 2008