CONSTANT-TIME GRAPH ALGORITHMS ON THE RECONFIGURABLE MULTIPLE BUS MACHINE

The reconfigurable multiple bus machine (RMBM) is a model of parallel computation based on reconfigurable buses, Unlike other reconfigurable bus-based models such as the reconfigurable mesh (R-Mesh), the RMBM s eparates the functions of processors and switches, In this paper, we p resent constant time RMBM algorithms for a number of fundamental graph problems. These algorithms are more efficient, in terms of processors , than corresponding R-Mesh algorithms, Also presented is a novel rang e reduction technique for a constant time simulation of each step of a Priority CRCW RMBM on a Common or Collision CRCW RMBM, This simulatio n incurs only a factor of O(P-epsilon) increase in the number of proce ssors and buses, where epsilon > 0 is any constant and P is the number of processors in the simulated Priority CRCW RMBM, This method may be of independent interest. The algorithms presented in this paper demon strate the potential for fast and processor-efficient computation avai lable in the ability of a reconfigurable bus-based model to separate t he functions of processors and switches. (C) 1991 Academic Press.