# What is a best known algorithm for finding diameter of undirected graph? [duplicate]

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

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