Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• The mesh-connected computers with hyperbus broadcasting are an extension of the mesh-connected computers with multiple broadcasting. Instead of using local buses, we use global buses to connect processors. Such a strategy efficiently reduces 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(logN) and O(log^2 N) time, 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 problem, the minimum spanning tree problem and the bipartite graph recognition problem can be solved in the order of polylogarithmic time.

• 一般社団法人電子情報通信学会の論文
• 1996-08-25

著者

• Horng S‐j

  National Taiwan Univ. Sci. And Technol. Taipei Twn

• Horng Shi-jinn

  Department Of Electrical Engineering National Taiwan University Of Science And Technology

関連論文

• Parallel Algorithms for Higher-Dimensional Euclidean Distance Transforms with Applications(Special Issue on Parallel and Distributed Computing, Applications and technologies)
• Generalized Mesh-Connected Computers with Hyperbus Broadcasting for a Computer Network (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)

スポンサーリンク