|DATE:||Wednesday, October 17th|
|TIME:||4:30 PM - 5:30 PM|
|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.