Clique-Width: Harnessing the Power of Atoms
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422372" target="_blank" >RIV/00216208:11320/20:10422372 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/chapter/10.1007%2F978-3-030-60440-0_10" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-030-60440-0_10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-60440-0_10" target="_blank" >10.1007/978-3-030-60440-0_10</a>
Alternative languages
Result language
angličtina
Original language name
Clique-Width: Harnessing the Power of Atoms
Original language description
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 if they are so on the atoms (graphs with no clique cut-set) of . 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 (????1,????2) -free if it is both ????1 -free and ????2 -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 (????1,????2) -free graphs, as evidenced by one known example. We prove the existence of another such pair (????1,????2) and classify the boundedness of clique-width on (????1,????2) -free atoms for all but 18 cases.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph-Theoretic Concepts in Computer Science. WG 2020.
ISBN
978-3-030-60439-4
ISSN
—
e-ISSN
—
Number of pages
15
Pages from-to
119-133
Publisher name
Springer
Place of publication
Cham
Event location
Leeds, Great Brittain
Event date
Jun 24, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—