Project Details
Projekt Print View

Algorithmik großer dynamischer geometrischer Graphen

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
Participating Person Professor Dr. Christian Sohler
 
 

Additional Information

Textvergrößerung und Kontrastanpassung