My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here:
I have a large, connected, sparse graph in adjacency-list form. I would like to find the diameter of the graph and two vertices achieving it.
Is there a better approach than computing all-pairs shortest paths?
I am interested in this problem in both the undirected and directed cases, for different applications. In the directed case, I of course care about directed distance (the maximum over pairs of vertices of the length of the shortest directed path from the first vertex to the second).
Best Answer
It's only helpful in the dense case, not the sparse case that you're asking about, but Yuster has recently shown that the diameter of an unweighted directed graph can in fact be computed more efficiently than known algorithms for all pairs shortest paths. See his paper "Computing the diameter polynomially faster than APSP" on arXiv:1011.6181.