Authors: Sawitzki, Daniel
Title: Algorithmik und Komplexität OBDD-repräsentierter Graphen
Language (ISO): de
Abstract: 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.
Subject Headings: Algorithmen
Komplexität
Graphen
OBDDs
URI: http://hdl.handle.net/2003/23118
http://dx.doi.org/10.17877/DE290R-67
Issue Date: 2006-12-07T16:38:05Z
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
DISS.PDFDNB1.45 MBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.