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

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