Re: [graph-tool] graph-tool Digest, Vol 77, Issue 6
Just DFS? Isn't that slow? Maybe Tarjan's? Or Newman-Ziff's? On Tue, Jun 10, 2014 at 5:30 PM, <graph-tool-request@skewed.de> wrote:
Send graph-tool mailing list submissions to graph-tool@skewed.de
To subscribe or unsubscribe via the World Wide Web, visit http://lists.skewed.de/mailman/listinfo/graph-tool or, via email, send a message with subject or body 'help' to graph-tool-request@skewed.de
You can reach the person managing the list at graph-tool-owner@skewed.de
When replying, please edit your Subject line so it is more specific than "Re: Contents of graph-tool digest..."
Today's Topics:
1. Algorithm to find the largest connected cluster (Shubham Bhushan) 2. Re: Algorithm to find the largest connected cluster (Tiago de Paula Peixoto)
----------------------------------------------------------------------
Message: 1 Date: Tue, 10 Jun 2014 11:01:39 +0530 From: Shubham Bhushan <shubphotons@gmail.com> To: graph-tool@skewed.de Subject: [graph-tool] Algorithm to find the largest connected cluster Message-ID: <CACpvG2HkeACyDVLhkwUw2= qxtpj2chR8ROCYostkiPhz+f+HrA@mail.gmail.com> Content-Type: text/plain; charset="utf-8"
Hi I want to know what Algorithm Graph Tool uses to find the larges connected cluster. If possible provide me the links to research paper/book/blog where the algorithm is discussed. Shubham
On 06/10/2014 02:36 PM, Shubham Bhushan wrote:
Just DFS? Isn't that slow? Maybe Tarjan's? Or Newman-Ziff's?
It *is* Tarjan's algorithm, which is just a DFS over the nodes. It has linear complexity, so it is not slow. Newman-Ziff is for growing networks, so it does not apply here. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Shubham Bhushan -
Tiago de Paula Peixoto