期刊
ALGORITHMS
卷 13, 期 9, 页码 -出版社
MDPI
DOI: 10.3390/a13090216
关键词
graph analytics; parallel graph algorithms; weighted graph decomposition; weighted diameter approximation; MapReduce
资金
- MIUR, the Italian Ministry of Education, University and Research, under PRIN [20174LF3T8]
- University of Padova
- NSF [CCF 1740741, IIS 1813444]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据