Uploaded image for project: 'Giraph'
  1. Giraph
  2. GIRAPH-1135

Implementing Minimum Spanning Tree in vertex-centric model

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: examples
    • Labels:

      Description

      A Minimum Spanning Tree is a tree that spans all the vertices of a connected graph such that the sum of the weights is minimum among all possible such trees. Finding Minimum Spanning Tree on a large graph has many applications. MST algorithm is one of the basic graph algorithms. Currently, Giraph has an implementation of Page Rank algorithm as part of its source code. An implementation of MST algorithm will strengthen our use cases.

      Recently Mohsen Ghaffari et al. have shown that MST can be calculated in O(log* n) rounds of communications in Congested Clique model [1]. Congested Clique have been shown to be the impromptu distributed algorithmic model which has direct relations with Pregel. We can try to implement the paradigm in Giraph.

      [1] MST in Log-Star Rounds of Congested Clique :- http://dl.acm.org/citation.cfm?id=2933103

        Attachments

          Activity

            People

            • Assignee:
              Alessio Alessio Arleo
              Reporter:
              cmartella Claudio Martella
            • Votes:
              0 Vote for this issue
              Watchers:
              6 Start watching this issue

              Dates

              • Created:
                Updated: