McGill University - School of Computer Science

Algorithms Seminar Winter 2001

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.