[ https://issues.apache.org/jira/browse/GIRAPH1135?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel&focusedCommentId=15903971#comment15903971
]
Alessio Arleo edited comment on GIRAPH1135 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 vertexcentric model
> 
>
> Key: GIRAPH1135
> URL: https://issues.apache.org/jira/browse/GIRAPH1135
> 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 LogStar Rounds of Congested Clique : http://dl.acm.org/citation.cfm?id=2933103

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