Robuste Algorithmen zu algorithmischen Graphenproblemen, eingeschränkt auf spezielle Graphenklassen

• Antragsteller: Professor Dr. Andreas Brandstädt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2000 bis 2004
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5246362

Grundlegende algorithmische Graphenprobleme treten in vielen Graphenmodellen der Informatik und diskreten Mathematik auf, und ihre effiziente Lösung ist Bestandteil vieler algorithmischer Problemlösungen. Wegen der NP-Vollständigkeit vieler dieser Probleme, ist es notwendig, auf der Suche nach effizienten Lösungen der Probleme die Problemstellung einzuschränken. Dies soll hier durch Einschränkung auf spezielle Graphenklassen geschehen. Schwerpunkt dabei soll die Entwicklung von robusten Algorithmen sein, die für eine spezielle Graphenklasse C zu beliebigem Eingabegraphen G entweder das vorgegebene algorithmische Problem II korrekt lösen oder feststellen, daß G nicht zur Klasse C gehört. Der robuste Algorithmus löst also das Problem für eine Oberklasse von C und vermeidet die Erkennung von C. Dies kann gegenüber dem herkömmlichen Vorgehen, bei dem die Erkennung der Graphenklasse Bestandteil der algorithmischen Lösung ist, von entscheidendem Vorteil bei der Komplexität der Lösung sein, wenn der robuste Algorithmus schneller als die Erkennung der Graphenklasse ist. Dafür gibt es wichtige Beispiele, und das Hauptanliegen des Projekts soll eine systematische Fortführung dieses Konzepts sein.

• DFG-Verfahren: Sachbeihilfen