Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Contributions to Clique-Width of Graphs

Hard Copy
EUR 19.00 EUR 18.05

E-book
EUR 13.30

Contributions to Clique-Width of Graphs (English shop)

Hoang-Oanh Le (Author)

Preview

Table of Contents, Datei (51 KB)
Preface, Datei (59 KB)
Extract, Datei (140 KB)

ISBN-13 (Printausgabe) 3865370136
ISBN-13 (Hard Copy) 9783865370136
ISBN-13 (eBook) 9783736910133
Language Alemán
Page Number 134
Edition 1 Aufl.
Volume 0
Publication Place Göttingen
Place of Dissertation Rostock
Publication Date 2004-03-11
General Categorization Dissertation
Departments Mathematics
Description

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.