Exakte Algorithmen für schwere Graphenprobleme | springerprofessional.de

Springer Professional

nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

Exakte Algorithmen für schwere Graphenprobleme

verfasst von: Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

Verlag: Springer Berlin Heidelberg

Buchreihe : eXamen.press

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dieses Buch befasst sich mit schweren Problemen auf Graphen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt verschiedene Methoden vor, wie man mit der algorithmischen Härte solcher Probleme umgehen kann. Einerseits kann man effiziente Algorithmen entwerfen, die sich eine geeignete Baumstruktur der Graphen zunutze machen; andererseits erlauben Fest-Parameter-Algorithmen eine effiziente Lösung, wenn gewisse Graphenparameter klein sind. Auch wenn diese Methoden nicht anwendbar sind, können die vorhandenen exakten Exponentialzeit-Algorithmen für solche schweren Probleme oft verbessert werden. Durch die leicht verständliche Darstellung, viele erklärende Abbildungen, Beispiele und Übungsaufgaben sowie die durchdachte Auswahl von Resultaten und Techniken ist dieses Buch besonders gut für den Einsatz in der Lehre geeignet, vor allem im Masterstudium Informatik und in den höheren Semestern des Bachelorstudiums Informatik. Gleichzeitig führt es den Leser unmittelbar an die Fronten der aktuellen Forschung in diesem neuen Teilgebiet der Algorithmik heran.

Anzeige

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung

Graphen sind hervorragend zur anschaulichen Darstellung von Beziehungen geeignet. Sehen wir uns ein Beispiel aus dem Alltag an: Ein Lehrer möchte mit seiner Klasse für ein paar Tage in eine Jugendherberge fahren. Nun überlegt er, wie viele Zimmer er reservieren muss, damit die Tage der Klassenfahrt für ihn so stressfrei wie möglich werden.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

Grundlagen

Frontmatter

2. Aufwandsabschätzung von Algorithmen

Zusammenfassung

Kauft man sich ein technisches Gerät (z. B. einen Anrufbeantworter), so schlägt man zunächst die beiliegende Bedienungsanleitung auf und hält sich dann – so gut man kann – an die Anweisungen, die darin zur Inbetriebnahme des Geräts beschrieben sind. Ist die Anleitung gut, so muss man sie nur einmal durchlesen und alle Schritte nur einmal ausführen. Danach funktioniert das Gerät: Der Anrufbeantworter steht anrufaufnahmebereit da.² Eine gute Anleitung ist ein Algorithmus.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

3. Graphen

Zusammenfassung

In der Einleitung wurde ein spezielles Graphenproblem anhand eines Alltagsbeispiels vorgestellt, das Färbbarkeitsproblem, mit dessen Lösung ein Lehrer versucht, seine Schüler so auf die Zimmer einer Jugendherberge zu verteilen, dass ihm Ärger während der Klassenfahrt möglichst erspart bleibt (siehe Abb. 1.1 und Abb. 1.2). In diesem Kapitel werden weitere Graphenprobleme eingeführt, die wir in diesem Buch untersuchen wollen. Zunächst benötigen wir einige grundlegende Begriffe und Definitionen der Graphentheorie.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

4. Logik

Zusammenfassung

„Wenn das Quadrat einer ganzen Zahl immer gerade ist, dann ist 7 ohne Rest¹³ durch 3 teilbar.“ Diese zahlentheoretische Aussage ist zweifellos wahr, auch wenn sie keinen großen Sinn ergibt. Es handelt sich hierbei um die logische Implikation

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

5. Komplexitätstheorie

Zusammenfassung

Wann ist ein Problem schwer? Warum ist ein Problem schwerer als ein anderes? Mit diesen Fragen befasst sich die Komplexitätstheorie. In Abschnitt 3.4 wurden ausgewählte Graphenprobleme vorgestellt, wie zum Beispiel das Färbbarkeitsproblem für Graphen, und es wurde erwähnt, dass alle diese Probleme „schwer“ sind. Was darunter zu verstehen ist, wird Inhalt dieses Kapitels sein.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

Exakte Algorithmen fur Graphen

6. Fest-Parameter-Algorithmen für ausgewählte Graphenprobleme

Zusammenfassung

In den Abschnitten 3.4 und 5.1 wurden einige Probleme vorgestellt, die NP-vollständig oder NP-hart sind, die sich also nicht in Polynomialzeit lösen lassen, außer wenn die für unwahrscheinlich gehaltene Gleichheit P = NP gelten würde. Dazu gehören auch viele wichtige Graphenprobleme, wie zum Beispiel die in Abschnitt 3.4 definierten NP-vollständigen Probleme Unabhängige Menge, Knotenüberdeckung, Partition in k unabhängige Mengen (auch bekannt als k-Färbbarkeit, siehe Satz 5.26), Partition in Cliquen, Dominierende Menge, Domatische Zahl und das Traveling Salesperson Problem sowie das NP-harte Unique Optimal Traveling Salesperson Problem, für das Papadimitriou [Pap84] zeigte, dass es vollständig für die Komplexitätsklasse P^NP ist.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

7. Exponentialzeit-Algorithmen für Färbbarkeitsprobleme

Zusammenfassung

Zunächst stellen wir in diesem Abschnitt ein paar Algorithmen vor, die auf einfachen Ideen beruhen und den naiven Algorithmus für Dreifärbbarkeit bereits schlagen (auch wenn sie natürlich immer noch Exponentialzeit brauchen; schließlich ist das Dreifärbbarkeitsproblem nach Satz 5.26 NP-vollständig). Anschließend gehen wir kurz auf die Motivation für exakte Exponentialzeit-Algorithmen ein und erläutern, weshalb solche Verbesserungen für praktische Anwendungen sehr sinnvoll sein können.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

8. Exponentialzeit-Algorithmen für TSP und DNP

Zusammenfassung

Im vorigen Kapitel haben wir eine Technik kennen gelernt, mit der sich die naiven Exponentialzeit-Algorithmen für eine Vielzahl von Problemen deutlich verbessern lassen, nämlich alle die Probleme, die sich für positive natürliche Zahlen a und b als (a, b)-CSP darstellen lassen. Dies gelingt für ganz unterschiedliche Probleme, etwa das Erfüllbarkeitsproblem der Aussagenlogik und Färbbarkeitsprobleme auf Graphen, aber nicht für alle Probleme.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

Algorithmen auf speziellen Graphen

Frontmatter

9. Bäume und Co-Graphen

Zusammenfassung

Wie bereits in Kapitel 3 erläutert, gibt es zahlreiche spezielle Graphklassen. Lassen sich alle Graphen einer Klasse entlang einer Baumstruktur aufbauen, so spricht man von einer baumstrukturierten Graphklasse. 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. Voraussetzung für diese effiziente Analyse ist, dass die Baumstruktur der Graphen explizit gegeben ist bzw.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

10. Baumweitebeschränkte Graphen

Zusammenfassung

Nun betrachten wir Parametrisierungen, die die Weite eines Graphen messen, wenn dieser in einer speziellen Baumstruktur repräsentiert wird. Entlang dieser Baumstruktur können viele an sich schwere Probleme auf Graphen mit beschränktem Parameter effizient im Sinne von FPT-Algorithmen gelöst werden.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

11. Cliquenweitebeschränkte Graphen

Zusammenfassung

In diesem Kapitel werden wir einen zweiten Ansatz zur Lösung schwieriger Graphenprobleme auf speziellen Baumstrukturen kennen lernen. Im Gegensatz zum Ansatz über die Baumweite wird es im folgenden Ansatz auch möglich sein, im Sinne der Fest-Parameter-Algorithmik solche Instanzen effizient zu lösen, die beliebig dichte Graphen (z. B. vollständige Graphen oder vollständig bipartite Graphen) enthalten. Dazu werden wir den Graphparameter Cliquenweite und seinen algorithmischen Nutzen vorstellen.

Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke

Backmatter

Titel: Exakte Algorithmen für schwere Graphenprobleme
verfasst von: Frank Gurski
Irene Rothe
Jörg Rothe
Egon Wanke
Copyright-Jahr: 2010
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-04500-4
Print ISBN: 978-3-642-04499-1
DOI: https://doi.org/10.1007/978-3-642-04500-4

Weitere Formate
Fachgebiete
Bücher
Zeitschriften
Themenseiten
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024