Parallel directed graph algorithms on directional processor arrays with reconfigurable bus systems

Processors arrays with reconfigurable bus systems (abbreviated to PARBS) ha ve 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 direc ted graph problems. Therefore, in this paper, a model named D-PARBS (Direct ional 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 co mponent problems on directed graphs.