[
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15904423#comment-15904423
]
Mohit Daga commented on GIRAPH-1135:
------------------------------------
Hi [~cmartella]
Thanks for creating the Jira.
MST in Log-Star Rounds is the current state of the art given by theory
community.
I will work towards creating a proposal for this task as part of Google Summer
of Code.
Mohit
> 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)
