Publikation: Zeitschriftenartikel

Clique-width for 4-vertex forbidden subgraphs

Grunddaten
Abstract
Autoren
Einrichtung

Grunddaten

Titel	Clique-width for 4-vertex forbidden subgraphs
Veröffentlicht in	Theory of computing systems. - New York, NY : Springer
Erscheinungsjahr	2006
Seiten (von – bis)	561 – 590
Band	39
Heft-Nr.	4
Jahr	2006
Publikationsform	Druckschrift
Publikationsart	Zeitschriftenartikel
Sprache	Englisch
Letzte Änderung	20.05.2019 13:41:26
Bearbeitungsstatus	durch UB Rostock abschließend validiert
Dauerhafte URL	http://purl.uni-rostock.de/fodb/pub/36690
Links zu Katalogen

Abstract

Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. The notion of clique-width extends the one of treewidth, since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.

Autoren

Brandstädt, Andreas
Engelfriet, Joost
Le, Hoang-Oanh
Lozin, Vadim V.

Einrichtung

IEF/Bereich Informatik