zbMATH — the first resource for mathematics

An optimal minimum spanning tree algorithm. (English) Zbl 0973.68534
Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1853, 49-60 (2000).
Summary: We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum spanning forest of a graph with \(n\) vertices and \(m\) edges that runs in time \(O({\mathcal T}^* (m,n))\) where \({\mathcal T}^*\) is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine.
Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for \({\mathcal T}^*\) are \({\mathcal T}^* (m,n)= \Omega(m)\) and \({\mathcal T}^* (m,n)= O(m\cdot \alpha(m,n))\), where \(\alpha\) is a certain natural inverse of Ackermann’s function.
Even under the assumption that \({\mathcal T}^*\) is super-linear, we show that if the input graph is selected from \(G_{n,m}\), our algorithm runs in linear time w.h.p., regardless of \(n\), \(m\), or the permutation of edge weights. The analysis uses a new martingale for \(G_{n,m}\), similar to the edge-exposure martingale for \(G_{n,p}\).
For the entire collection see [Zbl 0941.00034].

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms