Efficient systolic algorithm for finding bridges in a connected graph (Q1099959)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient systolic algorithm for finding bridges in a connected graph |
scientific article |
Statements
Efficient systolic algorithm for finding bridges in a connected graph (English)
0 references
1988
0 references
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.
0 references
VLSI
0 references
systolic algorithm
0 references
bridges
0 references
n-node connected graph
0 references
n\(\times n\) array of processing elements
0 references
area and time complexity
0 references
systolic array
0 references