Professor Matthew matthew.johnson2@durham.ac.uk
Head Of Department
Professor Matthew matthew.johnson2@durham.ac.uk
Head Of Department
G. Paesani
Professor Daniel daniel.paulusma@durham.ac.uk
Professor
Andreas Brandstädt
Editor
Ekkehard Köhler
Editor
Klaus Meer
Editor
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 .
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
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018). |
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 | Jul 31, 2018 |
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 |
Accepted Conference Proceeding
(321 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-030-00256-5_23.
Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
(2021)
Presentation / Conference Contribution
Computing subset transversals in H-free graphs
(2020)
Presentation / Conference Contribution
Steiner trees for hereditary graph classes
(2020)
Presentation / Conference Contribution
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2018)
Presentation / Conference Contribution
Computing subset transversals in H-free graphs
(2021)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search