Johnson, M. and Paesani, G. and Paulusma, D. (2020) 'Connected vertex cover for (sP1+P5)-free graphs.', Algorithmica., 82 (1). pp. 20-40.
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 s P2-free graphs for any integer s ≥ 1. We give a polynomial-time algorithm to solve the problem for (s P1 + P5)-free graphs for every integer s ≥ 0. Our algorithm can also be used for the Weighted Connected Vertex Cover problem.
|Full text:||(AM) Accepted Manuscript|
Download PDF (388Kb)
|Publisher Web site:||https://doi.org/10.1007/s00453-019-00601-9|
|Publisher statement:||This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-019-00601-9|
|Date accepted:||12 June 2019|
|Date deposited:||13 June 2019|
|Date of first online publication:||20 June 2019|
|Date first made open access:||20 June 2020|
Save or Share this output
|Look up in GoogleScholar|