Autor(en): | Sawitzki, Daniel |
Titel: | Algorithmik und Komplexität OBDD-repräsentierter Graphen |
Sprache (ISO): | de |
Zusammenfassung: | Ordered Binary Decision Diagrams (OBDDs) werden in vielen praktischen Anwendungsgebieten erfolgreich als Datenstruktur zur kompakten Repräsentation boolescher Funktionen eingesetzt. Auch sehr große Graphen werden in Bereichen wie CAD und Model Checking oft implizit durch boolesche Funktionen und OBDDs dargestellt. Diese Dissertation behandelt grundlegende graphtheoretische Probleme auf OBDD-repräsentierten Graphen und lotet die Möglichkeiten entsprechender OBDD-basierter Algorithmen aus. Zum einen werden neue Algorithmen vorgestellt und ihre Eigenschaften im Hinblick auf das Entwurfsziel sublinearer Heuristiken analysiert. Zum anderen werden Grenzen des Ansatzes durch komplexitätstheoretische Härteresultate und konkrete untere Schranken aufgezeigt. |
Schlagwörter: | Algorithmen Komplexität Graphen OBDDs |
URI: | http://hdl.handle.net/2003/23118 http://dx.doi.org/10.17877/DE290R-67 |
Erscheinungsdatum: | 2006-12-07T16:38:05Z |
Enthalten in den Sammlungen: | LS 02 Komplexitätstheorie und Effiziente Algorithmen |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
DISS.PDF | DNB | 1.45 MB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org