Cuvillier Verlag

35 Jahre Kompetenz im wissenschaftlichen Publizieren
Internationaler Fachverlag für Wissenschaft und Wirtschaft

Cuvillier Verlag

De En Es
Contributions to Clique-Width of Graphs

Printausgabe
EUR 19,00 EUR 18,05

E-Book
EUR 13,30

Contributions to Clique-Width of Graphs

Hoang-Oanh Le (Autor)

Vorschau

Inhaltsverzeichnis, Datei (51 KB)
Vorwort, Datei (59 KB)
Leseprobe, Datei (140 KB)

Das Konzept der Cliquenweite, eingeführt von Courcelle, Engelfriet und Rozenberg, kann als eine Verallgemeinerung des Konzepts Baumweite aufgefasst werden. Die formale Definition der Cliquenweite ist jedoch völlig verschieden von derjenigen der Baumweite: Cliquenweite geht von Graphen mit Knotenmarkierungen aus und verallgemeinert Cographen (d. h. P4-freie Graphen). Dieses Konzept ist deswegen so interessant, weil es – ähnlich dem Konzept der Baumweite und über dieses hinausgehend – einen einheitlichen Zugang zur effizienten Lösung vieler algorithmischer Graphenprobleme auf Graphenklassen beschränkter Cliquenweite liefert.

Zur Zeit gibt es zwei zentrale offene Probleme zum Thema Cliquenweite: das Erkennungsproblem derjenigen Graphen mit Cliquenweite höchstens k für eine Zahl k ≥ 4,
und das Charakterisierungsproblem der Graphen mit Cliquenweite höchstens k für
eine Zahl k ≥ 3.

In dieser Arbeit präsentieren wir neue, sehr eingeschränkte Graphenklassen mit unbeschränkter Cliquenweite und neue Graphenklassen mit beschränkter Cliquenweite. Die meisten dieser neuen Graphenklassen von beschränkter Cliquenweite sind durch verbotene Fortsetzungen des P4 definiert und sind natürliche Verallgemeinerungen der Cographen.

ISBN-13 (Printausgabe) 3865370136
ISBN-13 (Printausgabe) 9783865370136
ISBN-13 (E-Book) 9783736910133
Sprache Deutsch
Seitenanzahl 134
Auflage 1 Aufl.
Band 0
Erscheinungsort Göttingen
Promotionsort Rostock
Erscheinungsdatum 11.03.2004
Allgemeine Einordnung Dissertation
Fachbereiche Mathematik