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.

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