[Top][All Lists]

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

[igraph] Complexity of constructing an MST

From: Yulia Matveyeva
Subject: [igraph] Complexity of constructing an MST
Date: Fri, 08 Jul 2011 17:33:06 +0400

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. 

Sincerely yours,
Yulia Matveyeva,
Department of Statistical Modelling,
Faculty of Mathematics and Mechanics,
St Petersburg State University, Russia

reply via email to

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