| DATE: | Wednesday, April 25th (re-sheduled from April 11th) |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | Stars, Matchings and Hamiltonian Tours |
| SPEAKER: | Henk Meijer, Department of Computer Science, Queens University |
In this talk I will discuss a variety of ways of connecting a set of points in the plane. In particular, we will look at connections known as minimal Steiner stars, minimal stars, maximal matchings and maximal Hamiltonian cycles. As we will see, not all of these interconnection networks are easy to compute. However there are interesting relationships between the optimal lengths of the four different patterns. This allows us to formulate approximation algorithms that are guaranteed to find answers within certain bounds of the optimal values.
This talk does not assume any previous knowledge about this topic.
I expect that anyone with an interest in computing or mathematics
will be able to understand most of what I plan to say.