[
https://issues.apache.org/jira/browse/GIRAPH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15903971#comment-15903971
]
Alessio Arleo edited comment on GIRAPH-1135 at 3/9/17 10:22 PM:
----------------------------------------------------------------
I am currently working on a paper that needed to implement a version of
Pathfinder Network scaling* into the TLAV model. I had already decided to share
the code as a part of Giraph, so I would like to have this issue assigned to me.
*It is a generalization of MSTs: a Pathfinder network of a graph is the union
set of all the edges of all the possible MSTs of a graph.
was (Author: alessio):
I am currently working on a paper that needed me to implement a version of
Pathfinder Network scaling* into the TLAV model. I had already decided to share
the code as a part of Giraph, so I would like to have this issue assigned to me.
*It is a generalization of MSTs: a Pathfinder network of a graph is the union
set of all the edges of all the possible MSTs of a graph.
> 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)
