Robust graph algorithmus, restricted to special graphclasses

• Applicant: Professor Dr. Andreas Brandstädt
• Subject Area: Theoretical Computer Science
• Term: from 2000 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants