Hi, Codeforces.

Could anybody kindly tell me something about fast calculating radius and/or diameter of non-weighted undirected graph (definitions can be found here) ? Fast = faster, than in O(MN) (breadth-first searches from each vertex). Any results are welcome: probabilistic, good in average, good for sparse graphs, etc. Thanks.

wil93 and I once attended a conference about the theme. You can find some useful papers here, under "Fast Computation of the Neighbourhood Function and Distance Distribution", and here (look at the links in the bottom of the text). Hope this helps :)

Yep, the algorithm they presented was as follows:

`Dist(U,V)`

is better than the best diameter found then update it, else exit.The interesting thing is that the algorithm founds the diameter very soon.

If you want an approximate diameter, then you can stop manually after having done, say, K searches. The algorithm is then O(MK). It is worth noting that you will find very good results even with very small K.

When they presented this algorithm, they showed us the results and the running time of some test with (if I'm not mistaken) K = 10, compared to the O(MN) algorithm. It turned out that even with that value of K the diameter found was very close to the "best" one.

Yes, that seems to be cool thing to use in practice. But, as we discussed a bit earlier (in Russian, though =)), we can choose U in such unlucky way that we won't find precise diameter ever.

Well, in the real task that I approached graphs could be pretty dense, so there's no sense in "approximating" radii or diameters, as they were quite small.

Still, thanks for pointing out the papers and nice description!

Does it work for every kind of graphs?

(I am missing comment delete option :(. )

No, example below.

Yes it does. But it is an approximate algorithm, as you are running only K iterations (where K ~ 10 or more, depending on you). It is interesting as it finds quickly the optimal solution (the "optimal in average" K is relatively small, so using a fixed small K can works well). Maybe this algorithm isn't very reliable in programming contest, because of its "approximate" nature, but in practice it is good.

Tranvick is correct. I mistaken the problem. Many thanks.

You are wrong, it works only for trees.

We run BFS from A, then from B and answer will be 3. But really answer is 4(E — D).

Your algorithm is ok for get a tree's diameter, but it's wrong for get a graph's diameter.

Our group in Florence recently worked on the computation of the diameter of large real-world graphs. You can download our software at http://amici.dsi.unifi.it/lasagne. In the web site, all the references are also listed. I hope this helps.