Re: [igraph] Complexity of constructing an MST

[Minh Nguyen]

Hi,

On Fri, Jul 8, 2011 at 11:33 PM, Yulia Matveyeva
<address@hidden> wrote:
> that is used in the corresponding function
> is O( |V| + |E|),

I can tell you that you can find a minimum spanning tree in time
roughly the same as above.


> while in most traditional books on graph theory I have only found information 
> about algorithms
> having a complexity of O( |E| * log (|V|) ).

You can get a very efficient implementation [1,2] of minimum spanning
tree using Chazelle's soft heap. The soft heap implementation has been
shown to result in a deterministic algorithm with inverse Ackermann
complexity.


[1] B. Chazelle. A minimum spanning tree algorithm with
inverse-Ackermann type complexity. Journal of the ACM,
47(6):1028--1047, 2000.

[2] H. Kaplan and U. Zwick. A simpler implementation and analysis of
Chazelle’s soft heaps. In C. Mathieu, editor, SODA 2009: Proceedings
of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 477--485. SIAM, 2009.

-- 
Regards
Minh Van Nguyen