next up previous
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 tex2html_wrap_inline838 step algorithm for solving the minimum-cost spanning tree problem on an tex2html_wrap_inline834 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 tex2html_wrap_inline946 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 tex2html_wrap_inline960 is broadcast right and left from the diagonal cell tex2html_wrap_inline962 . Each cell tex2html_wrap_inline964 knows the value of tex2html_wrap_inline966 and computes

displaymath968

which is passed down to the next mesh row. After reaching mesh row i, matrix row i stays there until each matrix row l, tex2html_wrap_inline976 , above it has passed over it and then continues to propagate down, passing over the rest of the matrix rows. The output matrix tex2html_wrap_inline978 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