Algorithmik großer dynamischer geometrischer Graphen

• Antragsteller: Professor Dr. Friedhelm Meyer auf der Heide
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5322544

Wir wollen uns in diesem Projekt mit der Modellierung, Entwicklung und Evaluierung von Algorithmen für Probleme auf großen dynamischen geometrischen Graphen beschäftigen, wie sie z.B. bei Problemen der Computergraphik, der Verkehrsüberwachung, oder der Telekommunikation auftreten. Ein geometrischer Graph ist ein Graph, dessen Knoten mit Positionen im euklidischen Raum versehen sind. Dynamik entsteht in geometrischen Graphen häufig dadurch, dass sich Knoten auf verschiedene Art und Weise bewegen dürfen. Diese Bewegungen induzieren Veränderungen in der Struktur des Graphen. Über die bisher bekannten Ansätze hinaus, wollen wir in unsere Modellierung von Bewegung anwendungsspezifische Charakterisierung wie Geschwindigkeit, Vorhersagbarkeit und Einschränkung von Bahnen einbeziehen. In der ersten Antragsphase werden Labeling (Flugzeuge in Verkehrskontrollsystemen), Partitionierungsprobleme, und Walkthrough Animation jeweils für bewegliche Objekte im Vordergrund stehen. Da diese Probleme entweder aufgrund ihrer Komplexität oder der zu erwartenden Größe der Instanzen nicht exakt zu lösen sind, werden wir moderne algorithmische Techniken zur Behandlung groer Datenmengen wie I/O-effiziente Algorithmen, Property Testing und Streaming einsetzen.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke
• Beteiligte Person: Professor Dr. Christian Sohler