Efficient minimum spanning tree algorithms on the reconfigurable mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of ann-vertex undirected graph. One runs on ann×n reconfigurable mesh with time complexity ofO(log2n). The other runs with time complexity ofO(logn) on ann1+ε×n reconfigurable mesh, where 0<ε<1 is a constant. All these improve the previously known results on the reconfigurable mesh.