| DATE: | Wednesday, October 17th |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | Computing the Maximum Detour and Spanning Ratio of Planar Chains, Trees and Cycles |
| SPEAKER: | Pat Morin, School of Computer Science, McGill University |
The maximum detour and spanning ratio of an embedded graph G are
values that measure how well G approximates Euclidean space and the
complete Euclidean graph, respectively. In this talk we describe
O(n log n) time algorithms for computing the maximum detour and
spanning ratio of a polygonal chain. These algorithms solve open
problems posed in at least two previous works. We
also generalize these algorithms to find an O(n log^2 n) time
algorithm for computing the maximum detour or spanning ratio of a tree
and an O(n^3/2 log n) time algorithm for computing the
maximum detour or spanning ratio of a cycle.
This is joint work with Stefan Langerman and Mike Soss.