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

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