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
 

Project Description

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