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
Abstract:
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
Abstract:
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.