A Note on the Fast Computation of Transitive Closure ofGraphs and the Multiplication of Integer Matrices

Some algorithms for computing transitive closure of a graph and matrix multiplication in the Boolean semiring and in the rings of residues are compared. The bounds for the size and depth of the corresponding Boolean circuits are given.