Johnson, M. and Paesani, G. and Paulusma, D. (2020) 'Connected vertex cover for (sP1+P5)-free graphs.', Algorithmica., 82 (1). pp. 20-40.
Abstract
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (388Kb) |
| Status: | Peer-reviewed |
| 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
| Export: | |
| Look up in GoogleScholar |
