CODEWITHSUNDEEP
algorithmgraphperformancediameter-protocol
liv
liv

Reputation: 21

How do I find the diameter of a graph?

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 :)

Upvotes: 2

Views: 3376

Answers (1)

Chronial
Chronial

Reputation: 70853

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).

Upvotes: 4

Related Questions