[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Complexity of constructing an MST

From: Tamas Nepusz
Subject: Re: [igraph] Complexity of constructing an MST
Date: Fri, 08 Jul 2011 15:54:23 +0200
User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv: Gecko/20110516 Lightning/1.0b2 Thunderbird/3.1.10

Hi Yulia,

This is probably a copy-paste error in the documentation; the construction
of a minimum spanning tree of an *unweighted* graph can be done in O(|V| +
|E|). I strongly suspect that igraph_minimum_spanning_tree_prim was
implemented after igraph_minimum_spanning_tree_unweighted and the time
complexity was copied blindly. I believe that our implementation basically
uses a binary heap, so its time complexity should be O(|E| * log |V|). Note
that it is possible to get O(|E| + |V| * log |V|) when using a Fibonacci
heap, but the difference matters only for dense graphs.


On 07/08/2011 03:33 PM, Yulia Matveyeva wrote:
> Good afternoon, dear igraph-community.
>  I have read in the igraph-documentation  
> (igraph Reference Manual of Csardi and Nepusz that I got from the official 
> igraph web-site)
> that the complexity of the algorithm for constructing a minimum spanning tree
> that is used in the corresponding function
> is O( |V| + |E|),
> while in most traditional books on graph theory I have only found information 
> about algorithms
> having a complexity of O( |E| * log (|V|) ).
>  Is there a mistake or could someone please give me a link to the description 
> of the (new ?)
> optimized algorithm ?
> Thanks in advance. 

reply via email to

[Prev in Thread] Current Thread [Next in Thread]