Algorithmik und Komplexität OBDD-repräsentierter Graphen

Sawitzki, Daniel

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Wegener, Ingo	de
dc.contributor.author	Sawitzki, Daniel	-
dc.date.accessioned	2006-12-07T16:38:05Z	-
dc.date.available	2006-12-07T16:38:05Z	-
dc.date.issued	2006-12-07T16:38:05Z	-
dc.identifier.uri	http://hdl.handle.net/2003/23118	-
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-67	-
dc.description.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.	de
dc.format.extent	1487308 bytes	-
dc.format.mimetype	application/pdf	-
dc.language.iso	de	-
dc.subject	Algorithmen	de
dc.subject	Komplexität	de
dc.subject	Graphen	de
dc.subject	OBDDs	de
dc.subject.ddc	004	-
dc.title	Algorithmik und Komplexität OBDD-repräsentierter Graphen	de
dc.type	Text	de
dc.contributor.referee	Sauerhoff, Martin	de
dc.date.accepted	2006-11-29	-
dc.type.publicationtype	doctoralThesis	en
dc.identifier.urn	urn:nbn:de:hbz:290-2003/23118-2	-
dcterms.accessRights	open access	-
Appears in Collections:	LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:

File	Description	Size	Format
DISS.PDF	DNB	1.45 MB	Adobe PDF	View/Open

This item is protected by original copyright

View License

Show simple item record

This item is protected by original copyright rightsstatements.org