Algorithmik großer dynamischer geometrischer Graphen

• Applicant: Professor Dr. Friedhelm Meyer auf der Heide
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks
• Participating Person: Professor Dr. Christian Sohler