In this paper we show that minimum-cost spanning tree is a special
case of the closed semiring path-finding problem [1, sections
5.6-5.9,]. For a graph of *n* vertices, the path-finding
problem can be solved sequentially in steps by a dynamic
programming algorithm [7, 12] of which
the algorithms of Floyd [5] and Warshall
[15] are special cases. This dynamic programming
algorithm has a well known step implementation on an mesh-connected computer
[2, 3, 4, 6, 13].

Previously known minimum-cost spanning tree algorithms for the mesh [2, 11] are based on the recursive algorithm of Boruvka (also attributed to Sollin) [14, pp. 71-83,], which is complicated to implement. For example, the algorithm of [2] achieves steps by reducing the fraction of the mesh in use by a constant factor at each recursive call. The dynamic programming algorithm has the same asymptotic running time but is much simpler.

The rest of this paper consists of two short sections. In section 2 we show how to cast minimum-cost spanning tree as a path-finding problem. In section 3, we briefly describe an step mesh algorithm to solve the problem.

Sun Jul 21 23:35:52 EDT 1996