Minimum-Cost Spanning Tree as a Path-Finding Problem

In this paper we show that the minimum cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a nonrecursive algorithm for finding minimum-cost spanning trees on mesh-connected computers which has the same asymptotic running time as but is much simpler than the previous recursive algorithms.