Graphstrukturtheorie und algorithmische Anwendungen

• Applicant: Professorin Dr. Isolde Adler
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 203684084

Ein Durchbruch in der modernen Graphentheorie ist Robertsons und Seymours Beweis von Wagners Vermutung. Der in über 20 Veröffentlichungen publizierte Beweis liefert, neben zahlreichen Erkenntnissen über die Struktur von Graphen, die Existenz vieler überraschender Polynomialzeitalgorithmen. Allerdings sind die meisten dieser Algorithmen in der Praxis nicht verwendbar: Bei einigen führen viel zu große Konstanten zu impraktikablen Rechenzeiten, von anderen (den nicht-konstruktiven Algorithmen) wissen wir zwar, dass sie existieren, es ist aber nicht bekannt wie man sie formulieren kann.Im Projekt GalA sollen diese Konstanten genau untersucht und Algorithmen verbessert bzw. konstruktiv gemacht werden. Dazu sollen Methoden von Robertson und Seymour verfeinert und weiter entwickelt werden. Die Rechenzeit steht hier in engem Zusammenhang mit der Größe bestimmter in Graphen vorkommender Strukturen. Es sollen die kritischen Strukturen gefunden bzw. möglichst genau bestimmt werden. Damit sollen Routing-Algorithmen verbessert, Algorithmen für Compiler entwickelt und implementiert, sowie (in Kombination mit Methoden der Logik) Probleme der Anfrageauswertung auf Datenbanken klassifiziert werden.

• DFG Programme: Research Grants