2015/06/10 by Matteo Ceccarello, Andrea Pietracaprina, Ceccarello, Matteo +5
Computer Science · #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1506.03265
openalex publication_date 2015/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a space and time efficient practical parallel algorithm for\napproximating the diameter of massive weighted undirected graphs on distributed\nplatforms supporting a MapReduce-like abstraction. The core of the algorithm is\na weighted graph decomposition strategy generating disjoint clusters of bounded\nweighted radius. Theoretically, our algorithm uses linear space and yields a\npolylogarithmic approximation guarantee; moreover, for important practical\nclasses of graphs, it runs in a number of rounds asymptotically smaller than\nthose required by the natural approximation provided by the state-of-the-art\n\Δ-stepping SSSP algorithm, which is its only practical linear-space\ncompetitor in the aforementioned computational scenario. We complement our\ntheoretical findings with an extensive experimental analysis on large benchmark\ngraphs, which demonstrates that our algorithm attains substantial improvements\non a number of key performance indicators with respect to the aforementioned\ncompetitor, while featuring a similar approximation ratio (a small constant\nless than 1.4, as opposed to the polylogarithmic theoretical bound).\n