How do I find the diameter of a graph?

Question

hey i'm looking for an algorithm to find the diameter (the longest shortest path) in an undirected unweighted graph G=(V,E).

the best solution i found was to run BFS |V| times, running time: O(|V|*(|v|+|E|)). can anybody think of a more efficient solution? even if it's only a bit more efficient i'd like to hear your ideas !

thanks a lot :)

Answer 1

There is some very recent work by Crescenzi et al. on “On Computing the Diameter of Real-world Undirected Graphs.” (2013) that proposes an algorithm that runs in O(V*E) worst case, but O(V) in a lot of real-world applications (I assume that means sparse graphs).