A minimum spanning tree algorithm with inverse-Ackermann type complexity
Bernard Chazelle · Journal of the ACM · 2000
A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is 0 ( m α( m, n )), where α is the classical functional inverse of Ackermann's function and n (respectively, m ) is the number of vertices (respectively, edges). The algorithm is comparison-based : it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.
Cited by 328 works. doi:10.1145/355541.355562 Open-access PDF
Authors
References
- Data Structures and Network Algorithms
- Efficiency of a Good But Not Linear Set Union Algorithm
- Fibonacci heaps and their uses in improved network optimization algorithms
- Finding Minimum Spanning Trees
- An 0(|E|loglog|V|) algorithm for finding minimum spanning trees
- Davenport-Schinzel Sequences and their Geometric Applications
- On the History of the Minimum Spanning Tree Problem
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- A randomized linear-time algorithm to find minimum spanning trees
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths