Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Clique-Width: Harnessing the Power of Atoms

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:32:18Z
dc.abstract.enMany 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.
dc.abstract.plW pracy analizujemy strukturę grafów z zabronionymi indukowanymi podgrafami. Badamy, dla jakich klas grafów: - szerokość klikowa jest nieograniczona, ale - jeśli dodatkowo założymy, że graf nie ma klik rozcinających, szerokość klikowa staje się ograniczona. Pokazujemy przykład takiej klasy grafów (dotąd znany był tylko jeden), dowodzimy też, że wiele naturalnych klas nie ma tej własności.
dc.affiliationUniwersytet Warszawski
dc.conference.countryWielka Brytania
dc.conference.datefinish2020-06-26
dc.conference.datestart2020-06-24
dc.conference.placeLeeds
dc.conference.seriesInternational Workshop on Graph-Theoretic Concepts in Computer Science
dc.conference.seriesInternational Workshop on Graph-Theoretic Concepts in Computer Science
dc.conference.seriesshortcutWG
dc.conference.shortcutWG 2020
dc.conference.weblinkhttps://algorithms.leeds.ac.uk/wg2020/
dc.contributor.authorNovotná, Jana
dc.contributor.authorMasařik, Tomáš
dc.contributor.authorRzążewski, Paweł
dc.contributor.authorDabrowski, Konrad
dc.contributor.authorPaulusma, Daniël
dc.date.accessioned2024-01-24T19:26:00Z
dc.date.available2024-01-24T19:26:00Z
dc.date.issued2020
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1007/978-3-030-60440-0_10
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/103154
dc.identifier.weblinkhttps://link.springer.com/chapter/10.1007%2F978-3-030-60440-0_10
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages119-133
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enclique-width
dc.subject.enH-free graphs
dc.subject.plszerokość klikowa
dc.subject.plgrafy bez H
dc.titleClique-Width: Harnessing the Power of Atoms
dc.typeJournalArticle
dspace.entity.typePublication