Skip to main content

Research Repository

Advanced Search

Connected Vertex Cover for (sP1+P5)-free graphs

Johnson, M.; Paesani, G.; Paulusma, D.

Connected Vertex Cover for (sP1+P5)-free graphs Thumbnail


Authors

G. Paesani



Contributors

Andreas Brandstädt
Editor

Ekkehard Köhler
Editor

Klaus Meer
Editor

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 sP2 -free graphs for any integer s≥1 . We prove that it is also polynomial-time solvable for (sP1+P5) -free graphs for every integer s≥ 0 .

Citation

Johnson, M., Paesani, G., & Paulusma, D. (2018). Connected Vertex Cover for (sP1+P5)-free graphs. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings (279-291). https://doi.org/10.1007/978-3-030-00256-5_23

Conference Name 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018).
Conference Location Cottbus, Germany
Start Date Jun 27, 2018
End Date Jun 29, 2018
Acceptance Date Jul 15, 2018
Online Publication Date Sep 2, 2018
Publication Date Sep 2, 2018
Deposit Date Jul 30, 2018
Publicly Available Date Mar 29, 2024
Pages 279-291
Series Title Lecture notes in computer science
Series Number 11159
Series ISSN 0302-9743,1611-3349
Book Title Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings.
ISBN 9783030002558
DOI https://doi.org/10.1007/978-3-030-00256-5_23
Public URL https://durham-repository.worktribe.com/output/1144185

Files





You might also like



Downloadable Citations