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:

This entry was posted on Thursday, September 7th, 2017 at 12:20 am and is filed under 2017, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.