ProV Logo
0
An improved algorithm for the vertex cov...
Bai, Zongwen...

Free

An improved algorithm for the vertex cover P3 problem on graphs of bounded treewidth by Bai, Zongwen ( Author )
Lemonjar Open Access
N.A
31-03-2016
Given a graph G=(V,E) and a positive integer t≥2, the task in the vertex cover Pt (VCPt) problem is to find a minimum subset of vertices F⊆V such that every path of order t in G contains at least one vertex from F. The VCPt problem is NP-complete for any integer t≥2 and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time 4p⋅nO(1) for the VCP3 problem on n-vertex graphs with treewidth p. In this paper, we propose an improvement of it and improved the time-complexity to 3p⋅nO(1). The connected vertex cover P3 (CVCP3) problem is the connected variation of the VCP3 problem where G[F] is required to be connected. Using the Cut\&Count technique, we give a randomized algorithm with runtime 4p⋅nO(1) for the CVCP3 problem on n-vertex graphs with treewidth p.
-
Article
pdf
36.88 KB
English
-
MYR 0.01
-
https://arxiv.org/abs/1603.09448
Share this eBook