Finding minimum spanning trees in O(m (m; n)) time

We describe a deterministic minimum spanning tree algorithm running in time O(m (m; n)), where is a natural inverse of Ackermann's function and m and n are the number of edges and vertices, respectively. This improves upon the O(m (m; n) log (m; n)) bound established by Chazelle in 1997. A similar O(m (m; n))-time algorithm was discovered independently by Chazelle, predating the algorithm presented here by many months. This paper may still be of interest for its alternative exposition.

我们描述了一种确定性的最小生成树算法，其运行时间为\(O(m\alpha(m,n))\)，其中\(\alpha\)是阿克曼函数的一个自然逆函数，\(m\)和\(n\)分别是边数和顶点数。这改进了1997年沙泽勒（Chazelle）所确定的\(O(m\alpha(m,n)\log\alpha(m,n))\)的界限。沙泽勒独立发现了一种类似的运行时间为\(O(m\alpha(m,n))\)的算法，比这里介绍的算法早了好几个月。本文因其不同的阐述方式可能仍然具有研究价值。