Analyse von Graphparametern für gerichtete Graphen

• Antragsteller: Privatdozent Dr. Frank Gurski
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 388221852

In diesem Projekt beschäftigen wir uns mit der Analyse von Graphparametern für gerichtete Graphen. Hierzu betrachten wir gerichtete Formen der Cliquenweite, NLC-Weite und Rangweite sowie verschiedene Ansätze für eine gerichtete Form der Baumweite. Es sollen sowohl graphentheoretische Ergebnisse als auch Fortschritte in der Algorithmik spezieller Graphen erzielt werden.Dieses Forschungsvorhaben verfolgt die folgenden Hauptziele. (1.) Die Weite spezieller gerichteter Graphklassen soll bzgl. bekannter Parameter untersucht werden. Hierzu zählen sowohl obere als auch untere Schranken für die Weite. (2.) Die Struktur aller gerichteten Graphen mit Weite höchstens k soll für verschiedene Parameter charakterisiert werden. (3.) Es soll ein Fortschritt in der Bestimmung der den gerichteten Parametern zugrundeliegenden Baumstrukturen erzielt werden. (4.) Die Lösbarkeit von schweren Graphenproblemen auf Graphen mit beschränkter gerichteter Weite soll näher untersucht werden. (5.) Die praktische Anwendbarkeit von Algorithmen soll experimentell ausgewertet werden.

• DFG-Verfahren: Sachbeihilfen