[
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15903976#comment-15903976
]
Claudio Martella commented on GIRAPH-1135:
------------------------------------------
what is the complexity of the solution you're looking into? This is actually
meant as a google summer of code project, we can open another issue for your
pathfinder network scaling problem.
> 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: Alessio Arleo
> Labels: gsoc2017
>
> 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)
