Algorithmik und Komplexität OBDD-repräsentierter Graphen

Simple item page
dc.contributor.advisorWegener, Ingode
dc.contributor.authorSawitzki, Daniel
dc.contributor.refereeSauerhoff, Martinde
dc.date.accepted2006-11-29
dc.date.accessioned2006-12-07T16:38:05Z
dc.date.available2006-12-07T16:38:05Z
dc.date.issued2006-12-07T16:38:05Z
dc.description.abstractOrdered 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.de
dc.format.extent1487308 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2003/23118
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-67
dc.identifier.urnurn:nbn:de:hbz:290-2003/23118-2
dc.language.isode
dc.subjectAlgorithmende
dc.subjectKomplexitätde
dc.subjectGraphende
dc.subjectOBDDsde
dc.subject.ddc004
dc.titleAlgorithmik und Komplexität OBDD-repräsentierter Graphende
dc.typeTextde
dc.type.publicationtypedoctoralThesisen
dcterms.accessRightsopen access

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
DISS.PDF
Size:
1.42 MB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.92 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen