Detailseite
Projekt Druckansicht

Effiziente Algorithmen für Probleme auf implizit, insbesondere durch BDDs beschriebenen Netzwerke

Antragsteller Professor Dr. Ingo Wegener (†)
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2001 bis 2008
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5314814
 
Bekannte Algorithmen zur Behandlung von Netzwerkproblemen stoßen bei großen Netzwerken an ihre Grenze. Dann können selbst Rechenzeiten, die Polynome kleinen Grades sind, zu groß sein. Darüber hinaus führt die Modellierung technischer Systeme, des Verkehrs und auch des WWW zu so großen Netzwerken, dass diese nicht mehr explizit, also durch Auflistung aller Knoten und Kanten, beschreibbar sind. Alternative Beschreibungsformen, in denen weder die Knoten noch die Kanten explizit genannt werden, heißen implizit. Die Behandlung der zentralen algorithmischen Probleme auf implizit beschriebenen Netzwerken stellt eine neue Herausforderung dar. In der ersten Phase werden BDD-basierte Netzwerkdarstellungen im Mittelpunkt der Untersuchungen stehen. Ziele sind die Entwicklung von BDD-basierten Netzwerkalgorithmen und ihre Analyse, Implementierung und Anwendung in anderen Projekten des Schwerpunktprogramms. Insbesondere sollen Eigenschaften von Netzwerken herausgefiltert werden, die bewirken, dass BDD-Darstellungen kompakt und BDD-basierte Algorithmen schnell sind.
DFG-Verfahren Schwerpunktprogramme
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung