# IPDPS paper available for download

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.