Next: 4 Acknowledgments Up: Minimum-Cost Spanning Tree as Previous: 2 Minimum-cost spanning tree

# 3 Implementation on a mesh-connected computer

In this section we give a short description of an step algorithm for solving the minimum-cost spanning tree problem on an mesh-connected computer. We assume that the diagonal element in each mesh row can broadcast a value to the other elements of the row in a single step. This type of broadcast can be simulated by a mesh without this capability by slowing the algorithm down by a constant factor [8, 9, 10]. The algorithm proceeds as follows. We assume that the input graph is given in the form of a matrix of edge costs which enters row-by-row through the top of the mesh. Matrix row i is modified as it passes over rows 1 through i-1 and is stored when it reaches mesh row i. When matrix row i passes over mesh row k, the value is broadcast right and left from the diagonal cell . Each cell knows the value of and computes

which is passed down to the next mesh row. After reaching mesh row i, matrix row i stays there until each matrix row l, , above it has passed over it and then continues to propagate down, passing over the rest of the matrix rows. The output matrix exits row-by-row from the bottom of the mesh. By theorem 1, the adjacency matrix of the minimum-cost spanning tree can be constructed by comparing the input and output matrices.

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