Logo des Repositoriums
 
Textdokument

Untere Schranken für heuristische Algorithmen

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2015

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

Dieser Beitrag ist eine deutschsprachige Zusammenfassung der Dissertation des Autors. In der Dissertation werden drei verwandte heuristische Verfahren zum Lösen schwerer Probleme untersucht: der k-Konsistenztest für das Constraint-Satisfaction-Problem, Resolution beschränkter Weite für 3-SAT und der Knotenpartitionierungsalgorithmus für das Graphisomorphieproblem. Die Hauptergebnisse der Dissertation sind untere Schranken an die Zeitkomplexität der Verfahren. In diesem Beitrag werden die untersuchten Verfahren eingeführt und die erzielten unteren Schranken vorgestellt.

Beschreibung

Berkholz, Christoph (2015): Untere Schranken für heuristische Algorithmen. Ausgezeichnete Informatikdissertationen 2014. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-419-6. pp. 31-40

Schlagwörter

Zitierform

DOI

Tags