Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4, D5
What and Who
Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time
Martin Kutz
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 30 June 2006
13:30
30 Minutes
Warning: Title has changed!
E1 4
Rotunda 3rd floor
Saarbrücken
Abstract
We present an algorithm that computes a shortest non-contractible
and a shortest non-separating cycle on an orientable combinatorial
surface of bounded genus in $O(n \log n)$ time, where $n$ denotes
the complexity of the surface. This solves a central open problem
in computational topology, improving upon the current-best
$O(n^{3/2})$-time algorithm by Cabello and Mohar (ESA 2005).
Our algorithm uses universal-cover constructions to find short
cycles and makes extensive use of existing tools from the field.
The result was presented at this year's SoCG.
Contact
Martin Kutz
119
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
We switched talks on very short notice. Sorry.
Kavitha's will give her talk in a couple of weeks.
Kavitha's will give her talk in a couple of weeks.
Martin Kutz, 06/30/2006 10:36
Martin Kutz, 06/30/2006 10:34 -- Created document.
Martin Kutz, 06/30/2006 10:34 -- Created document.