Detailseite
Projekt Druckansicht

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

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
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung