Mailing-List: contact giraph-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: giraph-dev@incubator.apache.org
Date: Mon, 26 Dec 2011 05:18:31 +0000 (UTC)
From: "Avery Ching (Resolved) (JIRA)" <jira@apache.org>
To: giraph-dev@incubator.apache.org
Message-ID: 
 <1656539290.44950.1324876711210.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <776280181.43966.1324718550683.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Resolved] (GIRAPH-115) Port of the HCC algorithm for
 identifying all connected components of a graph
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


     [ https://issues.apache.org/jira/browse/GIRAPH-115?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Avery Ching resolved GIRAPH-115.
--------------------------------

    Resolution: Fixed

I think work like this will really lower the bar for folks to try out Giraph. =)
                
> Port of the HCC algorithm for identifying all connected components of a graph
> -----------------------------------------------------------------------------
>
>                 Key: GIRAPH-115
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-115
>             Project: Giraph
>          Issue Type: New Feature
>    Affects Versions: 0.70.0
>            Reporter: Sebastian Schelter
>
> Port of the HCC algorithm that identifies connected components and assigns a componented id (the smallest vertex id in the component) to each vertex.
> The idea behind the algorithm is very simple: propagate the smallest vertex id along the edges to all vertices of a connected component until convergence. The number of supersteps necessary is equal to the length of the maximum diameter of all components + 1
> The original Hadoop-based variant of this algorithm was proposed by Kang, Charalampos, Tsourakakis and Faloutsos in "PEGASUS: Mining Peta-Scale Graphs", 2010
> http://www.cs.cmu.edu/~ukang/papers/PegasusKAIS.pdf

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira