Automatische Generierung von Algorithmen für Entscheidungs-, Optimierungs- und Enumerationsprobleme auf Graphen

• Antragsteller: Professor Dr. Peter Tittmann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2004
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5319782

Die Berechnung wichtiger Zuverlässigkeitskenngrößen für Kommunikationsnetze (Erreichbarkeit, Zusammenhangswahrscheinlichkeit, mittlere Bandbreite) ist ein NP-schwieriges algorithmisches Problem, d.h. ein Problem, für das der Rechenzeitaufwand exponentiell mit der Netzgröße wächst. Das Ziel des Vorhabens besteht in der Entwicklung leistungsfähiger und schneller Algorithmen für eine große Klasse von Netzen, die in der Graphentheorie durch eine beschränkte Weg- bzw. Baumweite beschrieben werden. Die vorgesehene Erweiterung der Theorie besteht in einer einheitlichen Beschreibung und einer automatischen Erzeugung solcher Algorithmen, die sich auch für die Berechnung weiterer NP-schwieriger Probleme der Graphentheorie eignen. Weiterhin soll gezeigt werden, dass diese Algorithmen auch für die approximative Bestimmung von Zuverlässigkeitskenngrößen in sehr großen Netzen geeignet sind. Neben theoretischen Ergebnissen bezüglich der Komplexität der Algorithmen soll die praktische Leistungsfähigkeit durch konkrete Implementationen demonstriert werden.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke