Effiziente Algorithmen für Temporale Graphen

• Antragsteller: Professor Dr. Frank Kammer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 571642628

Das Ziel dieses Projekts ist die Entwicklung effizienter Algorithmen für temporale Graphen. Wir betrachten Effizienz auf drei Arten: (1) Algorithmen, die Laufzeit optimieren, ohne die Lösungsqualität zu verschlechtern. (2) Platzeffiziente Algorithmen, die die asymptotische Laufzeit und Lösungsqualität von Standardalgorithmen beibehalten, aber den Speicherbedarf reduzieren. (3) Sublineare Algorithmen, die Probleme durch Randomisierung approximativ lösen, und dabei nur einen kleinen Teil der Eingabe betrachten. Für (1) betrachten wir hauptsächlich Probleme der temporalen Graph-Traversierung, wie der temporalen Erkundung, die einen temporalen Weg fordert, der alle Knoten eines gegebenen temporalen Graphen beinhaltet. Ein solcher Weg wird als Exploration Schedule bezeichnet. Erstens streben wir auf die Verbesserung der bekannten oberen und unteren Schranken für die Anzahl der Zeitschritte an, die für einen Exploration Schedule in bestimmten temporalen Graphen erforderlich sind. Zweitens zielen wir darauf ab, Heuristiken für die Berechnung von Exploration Schedules zu entwerfen. Andere Traversierungsprobleme von Interesse sind sogenannte agentenbasierte Probleme, wie zum Beispiel das temporale Rendezvous. Hier ist das Ziel, dass sich zwei Agenten in einem temporalen Graphen treffen. Wir wollen die Rechenleistung der Agenten auf polynomiale Zeit beschränken. Derzeitige Strategien für temporales Rendezvous benötigten eine superpolynomiale Rechenzeit. Für (2) konzentrieren wir uns auf platzeffiziente Varianten grundlegender temporaler Graphenalgorithmen zum Berechnen von bestimmten temporalen Wegen. Analog zu Tiefen- und Breitensuche in statischen Graphen sind solche Algorithmen oft die Basis zum Lösen komplexerer temporaler Probleme. Es existieren Linearzeit-Algorithmen, diese sind jedoch nicht platzeffizient. Darüber hinaus interessieren wir uns für speichereffiziente Datenstrukturen für temporale Graphen und deren kompakten oder succincten Darstellungen. Die bisherige Forschung über succincte temporale Graphdarstellungen hat sich kaum auf die Eingabeverteilung konzentriert, wie es bei statischen Graphen üblich ist. Zum Beispiel wurde viel Forschung zu succincten Darstellungen von planaren oder Intervall-Graphen durchgeführt. Unser Ziel ist es, succincte Darstellungen für eingeschränkte Klassen temporaler Graphen zu entwerfen. Zusätzlich fokussieren wir auf speichereffiziente Algorithmen für Iso- und Automorphismen bestimmter (temporaler) Graphenklassen. Für (3) betrachten wir sublineare Algorithmen, die bestimmte Eigenschaften temporaler Graphen approximieren. Es gibt derzeit keine sublinearen Algorithmen für temporale Graphen. Daher planen wir erste Ergebnisse für grundlegende Eigenschaften wie die Approximation des durchschnittlichen temporalen Knotengrades zu präsentieren. Weitere Beispiele beinhalten die Approximation der Anzahl temporärer Zusammenhangskomponenten und der frühesten Ankunftszeit von temporalen Wegen.

• DFG-Verfahren: Sachbeihilfen