科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given a graph G = (V, E), the task in the vertex cover P-3 (VCP3) problem is to find a minimum subset of vertices F subset of V such that every path of order 3 in G contains at least one vertex from F. The VCP3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker's EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP3 problem on planar graphs.
