27
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Practical Parallel Algorithm for Diameter Approximation of Massive Weighted Graphs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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 \(\Delta\)-stepping SSSP algorithm, which is its only practical linear-space competitor in the aforementioned computational scenario. We complement our theoretical 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).

          Related collections

          Most cited references6

          • Record: found
          • Abstract: not found
          • Conference Proceedings: not found

          R-MAT: A Recursive Model for Graph Mining

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Δ-stepping: a parallelizable shortest path algorithm

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A Randomized Parallel Algorithm for Single-Source Shortest Paths

                Bookmark

                Author and article information

                Journal
                2015-06-10
                2015-11-09
                Article
                1506.03265
                3ec58e3e-2344-4c60-be0d-ec7e640ef1af

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.DC

                Networking & Internet architecture
                Networking & Internet architecture

                Comments

                Comment on this article