3
$\begingroup$

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

http://snap.stanford.edu/data/com-Orkut.html

$\endgroup$
7
  • 2
    $\begingroup$ Especially when you also care about approximate methods, best in what sense? $\endgroup$
    – Juho
    Jan 14, 2015 at 18:45
  • $\begingroup$ Best in terms of time complexity $\endgroup$
    – php--
    Jan 14, 2015 at 19:01
  • 1
    $\begingroup$ If you're willing to settle for a 2-approximation, you can run BFS from an arbitrary node. $\endgroup$ Jan 14, 2015 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, 2015 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$ Jan 15, 2015 at 9:20

0