Home > News > Sergio Cabello: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

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

Date: 8. 1. 2017
Source: Discrete mathematics seminar
Torek, 10. 1. 2017, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. We show how to compute in O(n^{11/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(n^c) for some constant c<2.