Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs (Seminar DM)

Iz MaFiRaWiki

Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Sergio Cabello

Torek, 10. januar 2017, od 10h do 12h, Plemljev seminar, Jadranska 19


Povzetek:

We show how to compute in O(n11 / 6) expected time the diameter and the sum of the pairwise distances in a planar graph with n vertices. These are the first algorithms for this problem using time O(nc) for some constant c < 2.

Seminar za diskretno matematiko

Osebna orodja