FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik

Vortrag des Informatik-Kolloquiums 

Antrittsvorlesung:

Entwurf und Bewertung geometrischer Netzwerke

Geometrische Netzwerke sind Graphen, bei denen die Knoten Punkte in der Ebene sind. Diese Netzwerke tauchen in vielen Anwendungen auf, wie etwa dem Entwurf und der Bewertung von Verkehrsnetzen, dem VLSI-Chip-Layout, oder der Entwicklung und Analyse von Sensornetzen. Beim Entwurf und der Bewertung von geometrischen Netzwerken trifft man auf eine Vielzahl interessanter Fragen, die sowohl struktureller, als auch algorithmischer Natur sind. Wir stellen zunächst einige wichtige Bewertungskriterien für geometrische Netzwerke vor und zeigen dann an Hand einiger Beispiele, welchen Fragestellungen sich beim Entwurf und der Bewertung von geometrischen Netzwerken typischerweise ergeben. In vielen Anwendungen ist man etwa daran interessiert, planare Netzwerke zu konstruieren, bei denen das Verhältnis zwischen Weglänge im Netz und dem euklidischem Abstand (der so genannte Umweg) beschränkt ist. Wir zeigen, wie Netzwerke mit kleinem Umweg aussehen, und wie man zu einem gegebenen Netzwerk den Umweg berechnet. Weiterhin befassen wir uns mit dem Problem, wie man in einem gegebenen Netzwerk aufspannende Bäume mit möglichst wenigen Kreuzungen findet. Als weiteres Beispiel untersuchen wir, wie man ein Sensornetzwerk plant, so dass die Gesamtenergie zur Ablesung aller Sensoren möglichst klein wird.

  Ort: Takustr. 9, Hörsaal,  Zeit: Fr, 3.6.2005, 14 Uhr  s.t.