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(log² n). The other runs with time complexity ofO(logn) on ann ^1+ε×n reconfigurable mesh, where 0<ε<1 is a constant. All these improve the previously known results on the reconfigurable mesh. This work is supported by Ph.D. foundation of State Education Commission of China. WAN Yingyu was born in 1976. He received the B.S. degree in computer science from University of Science and Technology of China in 1997. Now he is a Ph.D. candidate in computer science of University of Science and Technology of China. His current research interests include parallel computing and combinatorial optimization. XU Yinlong was born in 1963. He received the B.S. degree in mathematics from Beijing University in 1983, and the M.S. degree in computer science from University of Science and Technology of China in 1989. His current research interests include parallel computing and combinatorial optimization algorithms. GU Xiaodong was born in 1975. He received the B.S. degree in computer science from University of Science and Technology of China in 1997. Now he is a Ph.D. candidate in computer science of University of Science and Technology of China. His current research interests include parallel computing and combinatorial optimization. CHEN Guoliang was born in 1938. He is a Professor and Ph.D. advisor in high performance parallel computing at University of Science and Technology of China. He is the Director of the National High Performance Computing Center at Hefei. His research interests include parallel computing, computer architecture, and combinatorial optimization.