giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Claudio Martella (JIRA)" <j...@apache.org>
Subject [jira] [Created] (GIRAPH-1135) Implementing Minimum Spanning Tree in vertex-centric model
Date Thu, 09 Mar 2017 20:57:38 GMT
Claudio Martella created GIRAPH-1135:
----------------------------------------

             Summary: Implementing Minimum Spanning Tree in vertex-centric model
                 Key: GIRAPH-1135
                 URL: https://issues.apache.org/jira/browse/GIRAPH-1135
             Project: Giraph
          Issue Type: Improvement
          Components: examples
            Reporter: Claudio Martella
            Assignee: Claudio Martella


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



--
This message was sent by Atlassian JIRA
(v6.3.15#6346)

Mime
View raw message