[
https://issues.apache.org/jira/browse/FLINK-1526?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15860265#comment-15860265
]
ASF GitHub Bot commented on FLINK-1526:
---------------------------------------
Github user greghogan commented on a diff in the pull request:
https://github.com/apache/flink/pull/3284#discussion_r100421089
--- Diff: docs/dev/libs/gelly/library_methods.md ---
@@ -242,6 +242,28 @@ The algorithm takes a directed, vertex (and possibly
edge) attributed graph as i
vertex represents a group of vertices and each edge represents a group of
edges from the input graph. Furthermore, each
vertex and edge in the output graph stores the common group value and the
number of represented elements.
+## Minimum Spanning Tree
+
+#### Overview
+This is an implementation of the distributed minimum spanning tree (MST)
algorithm. A minimum spanning tree for a connected and
+undirected graph is a subset of edges with minimum possible total edge
weight that connects all the vertices without cycles.
+One of the possible use cases for MST could be laying out cables that
connect all buildings with the minimum total cable length.
+
+#### Details
+Unlike a sequential version of the algorithm, a distributed MST algorithm
is based on the message-passing model.
+We use [vertex-centric iterations](#vertex-centric-iterations) to
implement the Borůvka algorithm described in
+[this paper](http://ieeexplore.ieee.org/abstract/document/508073/). As
there are different steps inside the iteration,
--- End diff --
Should we cite https://www.cs.ubc.ca/~condon/papers/chungcondon96.pdf?
> Add Minimum Spanning Tree library method and example
> ----------------------------------------------------
>
> Key: FLINK-1526
> URL: https://issues.apache.org/jira/browse/FLINK-1526
> Project: Flink
> Issue Type: Task
> Components: Gelly
> Reporter: Vasia Kalavri
> Assignee: Xingcan Cui
>
> This issue proposes the addition of a library method and an example for
> distributed minimum spanning tree in Gelly.
> The DMST algorithm is very interesting because it is quite different from
> PageRank-like iterative graph algorithms. It consists of distinct phases
> inside the same iteration and requires a mechanism to detect convergence of
> one phase to proceed to the next one. Current implementations in
> vertex-centric models are quite long (>1000 lines) and hard to understand.
> You can find a description of the algorithm [here |
> http://ilpubs.stanford.edu:8090/1077/3/p535-salihoglu.pdf] and [here |
> http://www.vldb.org/pvldb/vol7/p1047-han.pdf].
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
