Variabilität von dynamischen Knoteneinbettungen

• Antragsteller: Professor Dr. Martin Grohe; Professor Dr. Markus Strohmaier
• Fachliche Zuordnung: Theoretische Informatik ; Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 453349072

Algorithmen für Knoteneinbettungen haben die letzten 5 Jahre grosses Forschungsinteresse geweckt, wobei neuronale Algorithmen besondere Aufmerksamkeit erhielten. Viele aktuelle Knoteneinbettungsalgorithmen verwenden Zufallsprozesse die mehrere verschiedene Knoteneinbettungen auf Basis des selben Graphen unter fixen Parametern produzieren können. Diese Instabilitäten beeinflussen dabei mögliche Aufgaben die unter Zuhilfenahme von Knoteneinbettungen adressiert werden. Eine kürzliche Arbeit der beiden Projektantragsteller zeigt das derartige Instabilitäten Klassifikationsergebnisse besonders auf Instanzebene beeinflussen können. Dies gibt erste Hinweise für die Bedeutung von Instabilität für Knoteneinbettungsalgorithmen, insbesondere für dynamisch-entwickelnde Graphen. Im vorliegenden Projekt beabsichtigen wir ein tiefergehendes Verständnis von Knoteneinbettungen für dynamisch-entwickelnde Graphen zu erarbeiten, mit einem besonderen Schwerpunkt auf Variabilität. Darüberhinaus sollen effiziente Algorithmen entwickelt werden um die Variabilität von Knoteneinbettungen für dynamische Graphen zu kontrollieren. Zusammenfassend trägt diese Arbeit zur Entwicklung von systematischeren Ansätzen für die Einbettung von Knoten bei.

• DFG-Verfahren: Sachbeihilfen