Publication details for Professor Matthew JohnsonJohnson, M., Paesani, G. & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica 82(1): 20-40.
- Publication type: Journal Article
- ISSN/ISBN: 0178-4617, 1432-0541
- DOI: 10.1007/s00453-019-00601-9
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for sP 2
- free graphs for any integer s≥1
. We give a polynomial-time algorithm to solve the problem for (sP 1 +P 5 )
- free graphs for every integer s≥ 0
. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.