What is best (in terms of time complexity) known algorithm (approximate or exact) for finding diameter of a large undirected graph?

The diameter is defined as longest of shortest paths between any two nodes.

I know that naive solution takes O(nm) steps and is basically taking pairs of all vertices and finds distances between them.

This is very slow for large graphs, 2^20 nodes or more.

An example graph


  • 2
    $\begingroup$ Especially when you also care about approximate methods, best in what sense? $\endgroup$ – Juho Jan 14 '15 at 18:45
  • $\begingroup$ Best in terms of time complexity $\endgroup$ – php-- Jan 14 '15 at 19:01
  • 1
    $\begingroup$ If you're willing to settle for a 2-approximation, you can run BFS from an arbitrary node. $\endgroup$ – Yuval Filmus Jan 14 '15 at 20:56
  • $\begingroup$ How would 2 approximation work in this case? Looks like it would give different answer in each case. $\endgroup$ – php-- Jan 14 '15 at 21:39
  • $\begingroup$ @RB It is a worst-case 2-approximation. It will return a value between the actual diameter and 2x the actual diameter. $\endgroup$ – Tom van der Zanden Jan 15 '15 at 9:20