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

Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
Sergio Cabello
Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia
2017/09/26 Tue 4PM-5PM (Room 3433, Bldg. E6-1)
We show how to compute for n-vertex planar graphs in roughly O(n11/6) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(nc) for some constant c<2, even when restricted to undirected, unweighted planar graphs.

Tags: