You are not logged in |
n log log n) Tim
- Speaker(s)
- Jakub Łącki
- Affiliation
- Uniwersytet Warszawski
- Date
- May 12, 2011, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n. This speedup is obtained through the use of dense distance graphs combined with a divide-and-conquer approach.
Joint work with Piotr Sankowski.
