Multivariate Algorithmik temporaler Graphprobleme (MATE)

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 382063982

Wie in der ersten Projektphase zielen wir auf die Entwicklung effizienter (parametrisierter) Algorithmen für zentrale Problem im Kontext temporaler Graphen ab. Im Vergleich mit dem Vorantrag gibt es eine gewisse Themenverschiebung hinsichtlich behandelter Themen. Die nun zur Untersuchung näher geplanten Themen sind wie folgt:- Neue temporale Konzepte wie z.B. temporale Graphklassen, Parameter und Problemklassen;- Probleme in Bezug auf temporale Pfade und temporale Konnektivität;- Probleme im Kontext des Findens temporaler Teilgraphen.Wir wollen die gegenwärtige Fachliteratur erweitern in dem wir uns vorwiegend auf exakte kombinatorische Algorithmen im Kontext der multivariaten Komplexitätsanalyse konzentrieren. Unser Ziel ist also die Identifizierung relevanter Parametrisierungen und das Studium ihres Einflusses auf die Komplexität des jeweilig betrachteten Problems. Zu diesem Zweck wollen wir den Werkzeugkasten der parametrisierten Algorithmik um neue Ansätze erweitern, welche insbesondere temporale Aspekte der gegebenen Probleme miteinbeziehen. Auf diese Weise wollen wir sowohl zur Algorithmentheorie im Bereich temporaler Graphen beitragen als auch an praktischen Lösungen für temporale Probleme arbeiten.

• DFG-Verfahren: Sachbeihilfen