Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 25, 2011, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Yves Brise
The past decade has been active in what I like to call range assignment problems. Consider a set of points P in the plane, and imagine them as senders/receivers in a network. If you assign radii to each of these senders, and assume that a sender is able to send that far, what you get is a geometric connection graph on the points in P. One can now impose different properties on this graph, the most natural of which is probably that it should be strongly connected. Your range assignment should try to minimize some function of the radii while still maintaining that property. There are several parameters in this problem, and also a lot of variants, considering slightly different settings or generalizations. I'm going to try to give an overview of the results and techniques in this field. That includes settled cases, approximations, and hardness results.
Automatic MiSe System Software Version 1.4803M | admin login