K. K. Dabrowski
Clique-Width: Harnessing the Power of Atoms
Dabrowski, K. K.; Masařík, T.; Novotná, J.; Paulusma, D.; Rzążewski, P.
Authors
Contributors
I. Adler
Editor
H. Müller
Editor
Abstract
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of G . Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph G is H-free if H is not an induced subgraph of G, and it is (H1,H2) -free if it is both H1 -free and H2 -free. A class of H-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for (H1,H2) -free graphs, as evidenced by one known example. We prove the existence of another such pair (H1,H2) and classify the boundedness of clique-width on (H1,H2) -free atoms for all but 18 cases.
Citation
Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020). Clique-Width: Harnessing the Power of Atoms. In I. Adler, & H. Müller (Eds.), Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers (119-133). https://doi.org/10.1007/978-3-030-60440-0_10
Conference Name | WG 2020 |
---|---|
Conference Location | Leeds, England |
Start Date | Jun 24, 2020 |
End Date | Jun 26, 2020 |
Acceptance Date | Jul 15, 2020 |
Publication Date | 2020 |
Deposit Date | Jul 10, 2020 |
Publicly Available Date | Mar 28, 2024 |
Volume | 2301 |
Pages | 119-133 |
Series Title | Lecture notes in computer science |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers. |
ISBN | 9783030604394 |
DOI | https://doi.org/10.1007/978-3-030-60440-0_10 |
Public URL | https://durham-repository.worktribe.com/output/1140444 |
Files
Accepted Conference Proceeding
(418 Kb)
PDF
Copyright Statement
This is a post-peer-review, pre-copyedit version of an article published in Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-60440-0_10
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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