Name
Abstract | ||
|---|---|---|
We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Delta-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.3390/a13090216 | ALGORITHMS |
Keywords | DocType | Volume |
graph analytics, parallel graph algorithms, weighted graph decomposition, weighted diameter approximation, MapReduce | Journal | 13 |
Issue | Citations | PageRank |
9 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matteo Ceccarello | 1 | 36 | 6.24 |
| Andrea Pietracaprina | 2 | 131 | 16.33 |
| Geppino Pucci | 3 | 443 | 50.49 |
| Eli Upfal | 4 | 4310 | 743.13 |