Solving some combinatorial problems on arrays with one-way dataflow (Q1825042)

Among various systolic architectures the ones with unidirectional flow of data provide some advantage at least from hardware designer's point of view - see e.g. \textit{R. Buschke} and \textit{J. Vysko\v{v}} [Reasons, techniques and solutions for linear systolic systems with unidirectional data flow, CONPAR 88, Proc. Conf. (1988)]. The article reviewed considers design of linear systolic arrays of this type for the following problems: ranking the elements in a chain, rooting a spanning tree and computing biconnected components of a connected graph. It is shown that all these problems can be solved using one-dimensional systolic array with unidirectional dataflow. Moreover a chain ranking algorithm has an interesting property, i.e. input data enters the array in arbitrary order. Also a biconnectivity algorithm is a little bit unusual one - it reads the input twice, or reads two copies of the input data. It is not clear whether this property is proper for unidirectional flow of data in solving this problem.