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 an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log~2 n). The other runs with time complexity of O(log …