Strukturelle Graphtheorie und parametrisierte Komplexität

• Applicant: Professor Dr. Peter Rossmanith
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants
• International Connection: Czech Republic
• Participating Person: Professor Petr Hlineny, Ph.D.