Journal
ALGORITHMS
Volume 13, Issue 9, Pages -Publisher
MDPI
DOI: 10.3390/a13090216
Keywords
graph analytics; parallel graph algorithms; weighted graph decomposition; weighted diameter approximation; MapReduce
Funding
- MIUR, the Italian Ministry of Education, University and Research, under PRIN [20174LF3T8]
- University of Padova
- NSF [CCF 1740741, IIS 1813444]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available