Efficient systolic algorithm for finding bridges in a connected graph (Q1099959): Difference between revisions

A new systolic algorithm for finding bridges in an n-node connected graph is proposed in this paper. The algorithm is executable on an \(n\times n\) array of processing elements. It is shown that our algorithm is an improvement over the previously known algorithm for an n-node connected graph on an \(n\times n\) array of processing elements, as proposed by \textit{M. J. Atallah} and \textit{S. R. Kosaraju} [J. Assoc. Comput. Mach. 31, 649- 667 (1984; Zbl 0629.68073)]. The improvement both in area and time complexity is significant. Moreover, the control structure required for implementing the proposed algorithm on a systolic array is simpler.