<p>I think the best known algorithm for unweighted undirected graphs takes Õ(n^ω), where n = |V| and ω &lt; 2.376 is the exponent of fast matrix multiplication.  And O((|V|+|E|) * lg |V|) would give us Õ(n^2), which is better than the best known algorithm.  Look at the introduction section of <a href="http://arxiv.org/abs/1011.6181" rel="nofollow">http://arxiv.org/abs/1011.6181</a> for a brief survey and references.</p>
How to get te running time of the diameter of a graph?
<p>If you have a simple undirected graph G(V, E), how can you find the diameter of the graph in O((|V|+|E|) * lg |V|) running time?</p>