Re: [igraph] Complexity of constructing an MST

[Tamas Nepusz]

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.

-- 
Tamas

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. 
>