GENERALIZED MESH-CONNECTED COMPUTERS WITH HYPERBUS BROADCASTING FOR ACOMPUTER NETWORK

The mesh-connected computers with hyperbus broadcasting are an extensi on of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently re duces the time complexity of the semigroup problem from O(N) to O(log N). Also, the matrix multiplication and the transitive closure problems are solved in O(log N) and O(log(2) N) ti me, respectively. Then, based on these operations, several interesting problems such as the connected recognition problem, the articulation problem, the dominator problem, the bridge problem, the sorting proble m, the minimum spanning tree problem and the bipartite graph recogniti on problem can be solved in the order of polylogarithmic lime.