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
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke