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:
[Dateien anzeigen]Adobe PDF
[Details]679,1 KB in einer Datei
[ZIP-Datei erzeugen]
Dateien vom 09.02.2007 / geändert 09.02.2007
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:In Copyright
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
english
Benutzer
Status: Gast
Aktionen