Dokument: The Domatic Number Problem: Boolean Hierarchy Completeness and Exact Exponential-Time Algorithms
Titel: | The Domatic Number Problem: Boolean Hierarchy Completeness and Exact Exponential-Time Algorithms | |||||||
URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=3609 | |||||||
URN (NBN): | urn:nbn:de:hbz:061-20070215-082010-0 | |||||||
Kollektion: | Dissertationen | |||||||
Sprache: | Englisch | |||||||
Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
Medientyp: | Text | |||||||
Autor: | Riege, Tobias [Autor] | |||||||
Dateien: |
| |||||||
Beitragende: | Prof. Dr. Rothe, Jörg [Gutachter] Prof. Dr. Wanke, Egon [Gutachter] | |||||||
Stichwörter: | Domatic Number Problem, Exakte Exponentialzeitalgorithmen, Komplexitätstheorie, Boolesche Hierarchie, PolynomialzeithierarchieDomatic Number Problem, Exact Exponential-Time Algorithms, Complexity Theory, Boolean Hierarchy, Polynomial Hierarchy | |||||||
Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
Beschreibung: | Das Domatic Number Problem wird in verschiedenen Variationen aus komplexitätstheoretischer Sicht betrachtet. Dabei werden Vollständigkeitsresultate für die Klasse DP als auch für die höheren Stufen der Booleschen Hierarchie über NP erzielt. Außerdem werden exakte und randomisierte Algorithmen mit exponentieller Laufzeit für das Domatic Number Problem analysiert. | |||||||
Lizenz: | Urheberrechtsschutz | |||||||
Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik | |||||||
Dokument erstellt am: | 16.01.2007 | |||||||
Dateien geändert am: | 12.02.2007 | |||||||
Promotionsantrag am: | 20.12.2006 | |||||||
Datum der Promotion: | 20.12.2006 |