Detailseite
Projekt
Algorithm Engineering für geometrische Graphen
Antragstellerin
Professorin Dr. Petra Mutzel
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung seit 2022
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 459420781
In unserer Forschungsgruppe kommen Graphen direkt als Landkarten oder indirekt als ihre geometrischen Dualgraphen, als Shortcut-Graphen oder als Triangulationen vor. In diesem Projekt betrachten wir diese Strukturen als geometrische Graphen, d. h. als Graphen, die in die Ebene (oder eine Fläche) eingebettet sind. Diese Graphen sind oft spärlich, sogar planar, und ermöglichen daher effizientere Graphenalgorithmen als allgemeine Graphen. Wir entwickeln Algorithm Engineering Ansätze für die praktische Lösung von diskreten Optimierungsproblemen auf geometrischen Graphen, die in Verbindung mit den in unserer Forschungsgruppe studierten Clustering, Aggregations- und Vereinfachungsproblemen auftreten. Ein wichtiges Ziel ist die Beschleunigung und Qualitätsverbesserung von kombinatorischen und ganzzahligen linearen Programmierungsansätzen für diskrete (multikriterielle) Optimierungsprobleme auf geometrischen Graphen. Dies wird durch die sorgfältige Berücksichtigung der Graphtopologie und der (geometrischen) Struktur der gegebenen Eingabedaten erreicht, manchmal in Kombination mit Lernansätzen. Für manche dieser Probleme werden neue Ähnlichkeitsmaße für geometrische Graphen eine wichtige Rolle spielen, die wir gemeinsam mit B1 entwickeln werden. Ein weiterer wichtiger Bestandteil sind sorgfältig ausgearbeitete Datenstrukturen, die Anfragen über Graphen und interaktive Karten ermöglichen.Als ein Brückenprojekt werden wir gemeinsam mit B1 sicherstellen, dass die in den Projekten A1, A2 und A3 vorgeschlagenen theoretischen Konzepte und Algorithmen in den Geodäsieprojekten C1 und C2 eine geeignete Umsetzung finden. Unser Arbeitsprogramm ist eng mit allen anderen Teilprojekten verzahnt.
DFG-Verfahren
Forschungsgruppen
