Min-cuts and Shortest Cycles in Planar Graphs in O

Prelegent(ci)

Jakub Łącki

Afiliacja

Uniwersytet Warszawski

Termin

12 maja 2011 12:15

Pokój

p. 5870

Tytuł w języku angielskim

n log log n) Tim

Seminarium

Seminarium "Algorytmika"

---

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. 

---