Constant Time Algorithms for the Transitive Closure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus Systems
Constant Time Algorithms for the Transitive Closure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus Systems
复制标题
可重构总线系统处理器阵列上传递闭包的常数时间算法及一些相关图问题
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Gen
中科院分区：
文献类型：
--
作者：
Biing;Gen
O(1)时间内的传递闭包问题通过一种与传统求解方法有很大不同的新方法来解决。在具有可重构总线系统的处理器阵列上，提出了两种 O(1) 时间算法来计算无向图的传递闭包。一种是在具有可重构总线系统的三维n*n*n处理器阵列上设计的，另一种是在具有可重构总线系统的二维n/sup 2/*n/sup 2/处理器阵列上设计的，其中n是图中的顶点数。使用 O(1) 时间传递闭包算法，许多其他图问题都可以在 O(1) 时间内解决。这些问题包括识别二分图以及在无向图中查找连通分量、连接点、双连通分量、桥和最小生成树。 >
The transitive closure problem in O(1) time is solved by a new method that is far different from the conventional solution method. On processor arrays with reconfigurable bus systems, two O(1) time algorithms are proposed for computing the transitive closure of an undirected graph. One is designed on a three-dimensional n*n*n processor array with a reconfigurable bus system, and the other is designed on a two-dimensional n/sup 2/*n/sup 2/ processor array with a reconfigurable bus system, where n is the number of vertices in the graph. Using the O(1) time transitive closure algorithms, many other graph problems are solved in O(1) time. These problems include recognizing bipartite graphs and finding connected components, articulation points, biconnected components, bridges, and minimum spanning trees in undirected graphs. >