Strukturelle Graphtheorie und parametrisierte Komplexität

点击翻译按钮获取中文摘要

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.