Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 22, 2010
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041

Lecture - 14:15

Michael Kaufmann - Tübingen

On MST-embeddings of trees in the plane

In their seminal paper on Euclidean minimum spanning trees (EMSTs), Monma and Suri proved that any tree of maximum degree 5 admits a planar embedding as an EMST. The algorithm they presented constructs an embedding with 2^O(n^2) area. Furthermore they conjectured that is sometimes an exponential area is required to embed a tree of maximum degree 5 as am EMST. In the past, we gave polynomial area bounds for trees of maximum degree 4, and recently we were able to affirm the conjecture of Monma and Suri by proving a 2^Omega(n^2) lower bound for EMST embeddings of a certain class of trees. In the talk, I will give some insights in our contributions.

Colloquium - 16:00

Rik Sarkar - FU Berlin

Ricci Flow in Sensor Networks : Applications in Routing and Distributed Storage

Data storage and routing schemes for sensor networks frequently use locations of nodes as an aid to keep the methods simple and  efficient. The algorithms however do not work well when the sensors are in an irregularly shaped region that contains empty 'holes' where there are no sensors. In such cases, some methods fail, others overload certain parts of the network.
This talk is about using Ricci flow to find virtual coordinates for the network. The new embedding has a simpler geometry, and allows the basic algorithms to work efficiently.

Letzte Aktualisierung: 22.11.2010