Our IPDPS16 paper titled “A Practical Parallel Algorithm for Diameter
Approximation of Massive Weighted Graphs
” is available for download
at
IEEE-Xplore.


From the abstract of the paper:

We present a space and time efficient practical parallel algorithm
for approximating the diameter of massive weighted undirected graphs
on distributed platforms supporting a MapReduce-like
abstraction. The core of the algorithm is a weighted graph
decomposition strategy generating disjoint clusters of bounded
weighted radius. Theoretically, our algorithm uses linear space and
yields a polylogarithmic approximation guarantee, moreover, for
important practical classes of graphs, it runs in a number of rounds
asymptotically smaller than those required by the natural
approximation provided by the state-of-the-art Δ-stepping SSSP
algorithm, which is its only practical linear-space competitor in
the aforementioned computational scenario. We complement
ourtheoretical findings with an extensive experimental analysis on
large benchmark graphs, which demonstrates that our algorithm
attains substantial improvements on a number of key performance
indicators with respect to the aforementioned competitor, while
featuring a similar approximation ratio (a small constant less than
1.4, as opposed to the polylogarithmic theoretical bound).

The software implementing the algorithms presented in the paper is
available as Free Software here.