Dokument: Effiziente Algorithmen für baumstrukturierte Graphklassen

Titel:	Effiziente Algorithmen für baumstrukturierte Graphklassen
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=2653
URN (NBN):	urn:nbn:de:hbz:061-20031104-000653-2
Kollektion:	Dissertationen
Sprache:	Deutsch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	PD Dr. Gurski, Frank [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 1,78 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 09.02.2007 / geändert 09.02.2007
Beitragende:	Prof. Dr. Wanke, Egon [Gutachter] Prof. Dr. Rothe, Jörg [Gutachter]
Stichwörter:	spezielle Graphklassen, NLC-Weite, Cliquenweite, Baumweite, effiziente Algorithmen, Graphalgorithmen, Graphenspecial graph classes, NLC-width, clique-width, tree-width, graph algorithms, graphs
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibung:	Diese Arbeit beschäftigt sich mit der Cliquenweite und der NLC-Weite von ungerichteten Graphen. Die Cliquenweite wurde 1994 von Courcelle und Olariu eingeführt und basiert auf drei Operationen für knotenmarkierte Graphen. Die NLC-Weite wurde 1994 von Wanke eingeführt und basiert auf lediglich zwei Operationen für knotenmarkierte Graphen. In einem knotenmarkierten Graphen ist jeder Knoten mit einer positiven ganzen Zahl markiert. Die Operationen der Cliquenweite erlauben zwei bereits definierte Graphen disjunkt zu vereinigen, in einem bereits definierten Graphen jeden mit i markierten Knoten mit jedem mit j markierten Knoten zu verbinden und alle mit i markierten Knoten mit j zu markieren. Bei den Operationen der NLC-Weite ist die disjunkte Vereinigung mit der Kanteneinfügeoperation kombiniert. Für eine Menge von Markierungspaaren S wird in der disjunkten Vereinigung zweier definierter Graphen G und J, für jedes Paar (i,j) in S, jeder i-markierte Knoten aus G mit allen j-markierten Knoten aus J verbunden. Die zweite Operation markiert, für eine Funktion R, in einem bereits definierten Graphen jeden i-markierten Knoten mit R(i). Der rekursive Aufbau der Graphen beginnt immer mit einzelnen markierten Knoten. Die Cliquenweite bzw. NLC-Weite eines Graphen G ist die minimale Anzahl von verschiedenen Markierungen die insgesamt benötigt werden, um G mit den entsprechenden Operationen aufzubauen. Graphen mit beschränkter Cliquenweite bzw. beschränkter NLC-Weite besitzen aufgrund ihrer Definition eine Baumstruktur. Einige der interessantesten Ergebnisse dieser Arbeit stehen im Zusammenhang mit der Baumweite von Graphen. Die Menge der Graphen mit Baumweite höchstens k wurde 1986 von Robertson und Seymour definiert und ist äquivalent zur Menge der partiellen k-Bäume. Ein Graph ist ein partieller k-Baum, wenn er ein Teilgraph eines k-Baumes ist. k-Bäume sind wie folgt rekursiv definiert. Der vollständige Graph mit k Knoten ist ein k-Baum. Wird in einem k-Baum ein neuer Knoten eingefügt und dieser mit allen Knoten eines vollständigen Teilgraphen mit k Knoten verbunden, so ist das Ergebnis wieder ein k-Baum. Graphen mit beschränkter Baumweite besitzen ebenfalls eine Baumstruktur. Baumstrukturierte Graphen spielen in der Informatik eine wichtige Rolle, da eine unterliegende Baumstruktur sehr oft eine systematische und effiziente Analyse der entsprechenden Graphen ermöglicht. Die Grundidee besteht aus einer dynamischen Programmierung in der alle Teillösungen für die Teilgraphen berechnet werden, die durch Teilbäume der Baumstruktur repräsentiert werden. Falls die maximale Anzahl der Teillösungen unabhängig von der Größe der Teilgraphen ist, so können die entsprechenden Graphenprobleme auf den baumstrukturierten Graphen mit dynamischer Programmierung Bottom-Up entlang der gegebenen Baumstruktur in linearer Zeit gelöst werden. Wir nutzen in dieser Arbeit die Baumstruktur von Graphen mit beschränkter Cliquenweite und Graphen mit beschränkter NLC-Weite um NP-schwere Probleme mittels dynamischer Programmiertechniken in polynomieller Zeit zu lösen. Dazu geben wir ein Schema zur effizienten Lösung von Graphenproblemen auf Graphen mit beschränkter NLC-Weite an und verwenden dieses Schema um effiziente Algorithmen für die NP-schweren Graphenprobleme Partition in unabhängige Mengen (Knotenfärbung), Partition in Cliquen, Partition in vollständig bipartite Graphen, Partition in perfekte Matchings, Minimales maximales Matching, Partition in Wälder, Hamilton Weg, Knotendisjunkte Wege, Knotengrad beschränkte Teilgraphen, Knotenpartition und Kantenpartition zu bestimmen. Das zentrale Problem im Zusammenhang mit der Cliquenweite und der NLC-Weite besteht in der Berechnung der Cliquenweite bzw. NLC-Weite eines Graphen. Für das Problem "Hat ein gegebener Graph die Cliquenweite (NLC-Weite) höchstens k?" sind bisher nur für festes k kleiner gleich 3 bzw. festes k kleiner gleich 2 effiziente Algorithmen bekannt. Für größere Werte für k und für die Minimierung von k sind bis heute keine Lösungsmethoden mit polynomieller Laufzeit bekannt. Eines der wichtigsten Ergebnisse dieser Arbeit zeigt, dass sich die Cliquenweite eines Graphen mit beschränkter Baumweite in linearer Zeit bestimmen lässt. In dieser Arbeit werden Abschätzungen für die Cliquenweite und NLC-Weite beliebiger Graphen angegeben. Weiterhin werden die durch die Cliquenweite, NLC-Weite und Baumweite definierten Graphklassen bezüglich ihrer Inklusionen untereinander und mit anderen Graphklassen verglichen.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:	04.11.2003
Dateien geändert am:	12.02.2007
Promotionsantrag am:	03.11.2003
Datum der Promotion:	03.11.2003