SumSweep [P1,P5,P9,P14]

SumSweep is the first bound-refinement algorithm that is able to find diameter and radius in directed, not necessarily strongly connected graphs. This algorithm not only is more general than all previous counterparts, but it also outperforms them on directed, strongly connected graphs or undirected graphs. The algorithm is based on a clever combination of the sweep approach with an extension of the bound-refinement techniques developed by Takes and Kosters, in order to compute the diameter of undirected graphs. The Java code for SumSweep along with some sample graphs can be downloaded from the publication section of the home page of Michele Borassi.