Parallel directed graph algorithms on directional processor arrays with reconfigurable bus systems
Processors arrays with reconfigurable bus systems (abbreviated to PARBS) have been received a lot of attention in the last decade, and many undirected graph algorithms with constant time complexity have been proposed on PARBS. However, for a directed graph, it will be proved that connecting PARBS in the way proposed for undirected graphs generates paths which do not exist in the directed graph. This result may lead to incorrect solution for directed graph problems. Therefore, in this paper, a model named D-PARBS (Directional PARBS) is proposed for eliminating the non-existent paths. This model can be used to correctly identifying redundant arcs on directed graphs in constant time. Furthermore, by modifying the D-PARBS architecture, constant time algorithms with O(n(3)) processors are developed to solve topological sort, transitive closure, cyclic graph checking, and strongly connected component problems on directed graphs.
directed graphs processor array with reconfigurable bus system topological sort transitive closure cyclic graph checking strongly connected component