Weiterentwicklung Algorithmischer Temporaler Graphentheorie

• Antragsteller: Dr. Hendrik Molter
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 565381415

Das Ziel des Projekts "Weiterentwicklung Temporaler Graphentheorie" ist, temporale Graphen Algorithmik voranzutreiben, und neu gewonnene Einsichten auf Probleme anzuwenden, die in den Anwendungsgebieten von Transport- und sozialen Netzwerken motiviert sind. Temporale Graphen haben Kantenmengen, die sich in diskreten Zeitschritten verändern können. Sie sind ein vielseitiges Modell für dynamische Daten und sind daher wohl motiviert in Fällen, in denen dynamische Veränderungen und zeitabhängige Interaktionen eine wichtige Rolle spielen. Wir planen systematisch temporale Graphklassen und temporale Parameter (die Ähnlichkeit zu temporalen Graphklassen messen) zu erforschen, mit dem Ziel neue algorithmische Techniken für temporale Graphenprobleme zu entwickeln. Wir organisieren genaue Zielgebungen in zwei Arbeitspaketen, die algorithmische temporale Graphentheorie vorantreiben sollen. Zusätzlich schlagen wir zentrale Probleme in den genannten Anwendungsgebieten vor, die wir in vier Arbeitspakete unterteilen. Weil wir erwarten, dass die meisten Probleme NP-schwer sind, planen wir die parametrisierte Komplexität der Probleme zu analysieren und Parametrisierungen zu identifizieren, die sogenannte fixed-parameter Algorithmen zulassen. Geläufige Ansätze die Eingabeinstanzen einzuschränken oder Parametrisierungen zu finden verfehlen häufig deren temporales Verhalten sinnvoll einzuschränken. Um diesen Defiziten entgegenzuwirken möchten wir neu entwickelte algorithmische Werkzeuge anwenden.

• DFG-Verfahren: Sachbeihilfen