Efficient Algorithms for problems on implicity defined networks with a focus on networks represented by BBDs

• Applicant: Professor Dr. Ingo Wegener (†)
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks