next up previous
Next: 2 Minimum-cost spanning tree Up: Minimum-Cost Spanning Tree as Previous: Minimum-Cost Spanning Tree as

1 Introduction

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 tex2html_wrap_inline830 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 tex2html_wrap_inline838 step implementation on an tex2html_wrap_inline834 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 tex2html_wrap_inline838 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 tex2html_wrap_inline838 step mesh algorithm to solve the problem.

Bruce Maggs
Sun Jul 21 23:35:52 EDT 1996