[Top][All Lists]

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

Re: [igraph] Complexity of constructing an MST

From: Minh Nguyen
Subject: Re: [igraph] Complexity of constructing an MST
Date: Sat, 9 Jul 2011 00:10:42 +1000


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

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

Minh Van Nguyen

reply via email to

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