[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
- [igraph] Complexity of constructing an MST,
Yulia Matveyeva <=