Strukturelle Graphtheorie und parametrisierte Komplexität

• Antragsteller: Professor Dr. Peter Rossmanith
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2008 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 100452017

Viele algorithmische Probleme aus der realen Welt sind in voller Allgemeinheit komplexitätstheoretisch schwer. Die Theorie der parametrisierten Komplexität ist ein neues Konzept, solche schweren Probleme feiner zu analysieren, und für den Entwurf neuartiger Algorithmen, die solche Probleme auf praktischen Instanzen effizient lösen können. Im Gegensatz zu Heuristiken liefert dieser Ansatz garantierte Laufzeitschranken. Graphen sind kombinatorische Strukturen, die sich für die Modellierung diskreter Entscheidungs- und Optimierungsprobleme eignen. Strukturelle Graphtheorie hat sich beim Entwurf parametrisierter Algorithmen bereits als nützlich erwiesen. Die meisten schweren Probleme sind beispielsweise auf Graphen mit beschränkter Baumweite effizient lösbar. Wir planen, andere strukturelle Eigenschaften von Graphen auszunutzen, z.B. ihre branch-width, DAG-width, rank-width und ihre topologischen Eigenschaften. Unser Ziel besteht darin, neue Anwendungsgebiete der strukturellen Graphtheorie für den Entwurf parametrisierter Algorithmen zu entdecken, indem zwei Arbeitsgruppen aus beiden Gebieten eng zusammenarbeiten.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Tschechische Republik
• Beteiligte Person: Professor Petr Hlineny, Ph.D.