n log log n) Tim

Speaker(s)

Jakub Łącki

Affiliation

Uniwersytet Warszawski

Date

May 12, 2011, 12:15 p.m.

Room

room 5870

Title in Polish

Min-cuts and Shortest Cycles in Planar Graphs in O

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. 

---