Statische und Dynamische Graphzerlegungen

• Antragsteller: Professor Dr. Harald Räcke
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 498605858

Graphen sind ein einfaches und sehr vielseitiges Werkzeug zur Modellierung von Beziehungen zwischen Daten. Sie sind daher weit verbreitet, und effiziente Graphenalgorithmen sind erforderlich, um Fortschritte in vielen Bereichen der Informatik zu ermöglichen, z. B. in der Netzwerketheorie, der Computergrafik und im Data Mining. Das Ziel dieses Forschungsvorhabens ist es, grundlegende Techniken für die Entwicklung schneller Graphenalgorithmen zu verstehen, sowohl für statische Graphen als auch für sich dynamisch verändernde Graphen. Während die Probleme für statischen Graphen, die wir vorschlagen, an sich interessant sind, sind sie auch auch so gewählt, dass sie die Entwicklung schneller Algorithmen für dynamische Graphen ermöglichen.Die Forschung der letzten Jahre hat gezeigt, dass eine neuartige Methode zur Zerlegung eines Graphen, die so genannte schnelle Expander-Zerlegung, zu schnelleren Algorithmen für eine Vielzahl von Algorithmen für eine Vielzahl von Graphproblemen führen kann; und die Anwendung dieser Technik für dynamische Graphen hat gerade erst begonnen. Wir glauben, dass andere Arten von (hierarchischen) Graphzerlegungen, die sehr erfolgreich in Online- und Approximationsalgorithmen eingesetzt wurden, ebenfalls von diesen neuen Erkenntnissen profitieren können, wodurch sich ein großes Potenzial für Performanceverbesserungen im statischen Bereich ergibt. Darüber hinaus werden diese Performanceverbesserungen es dann auch erlauben diese Zerlegungen auf dynamischen Graphen zu verwenden, was den Werkzeugkasten für den Entwurf dynamischer Graphalgorithmen deutlich erweitert.Die algorithmischen Probleme, die wir vorschlagen, bestehen aus grundlegenden Graphproblemen, die sich in einer Vielzahl anderer Forschungsbereiche stellen, wie z.B. der Computergrafik, der Analyse sozialer Netzwerke, dem graphbasierten maschinellen Lernen, den Computernetzwerken mit Problemen wie Netzwerk-Routing und kürzesten Wegen und dem Operations Research.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Österreich
• Partnerorganisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Kooperationspartnerin: Professorin Monika Henzinger, Ph.D.