Abstract
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.
Similar content being viewed by others
REFERENCES
S. Warshall, ‘‘A theorem on Boolean matrices’’, J. ACM 9, 11–12 (1962). https://doi.org/10.1145/321105.321107
B. Roy, ‘‘Transitive et connexite,’’ C. R. Acad. Sci. 249 (6), 216–218 (1959).
V. L. Arlazarov, E. A. Dinitz, M. A. Kronrod, and I. A. Faradzhev, ‘‘On economical construction of the transitive closure of an oriented graph,’’ Dokl. Akad. Nauk SSSR 194, 487–488 (1970).
M. E. Furman, ‘‘Application of a method of rapid multiplication of matrices to the problem of finding the transitive closure of a graph,’’ Dokl. Akad. Nauk SSSR 194, 524 (1971).
A. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974).
W. J. Savitch, ‘‘Relationship between nondeterministic and deterministic tape complexities’’, J. Comput. Syst. Sci. 4, 177–192 (1970). https://doi.org/10.1016/S0022-0000(70)80006-X
V. Strassen, ‘‘Gaussian elimination is not optimal,’’ Numer. Math. 13, 554–556 (1969). doi 10.1007/BF02165411
M. J. Fisher and A. R. Meyer, ‘‘Boolean matrix multiplication and transitive closure,’’ in 12th IEEE Annual Symp. on Switching and Automata Theory, East Lansing, MI, USA, 1971, pp. 129–131. https://doi.org/10.1109/SWAT.1971.4
M. I. Grinchuk, ‘‘Sharpening an upper bound on the adder and comparator depths,’’ J. Appl. Ind. Math. 3, 61–67 (2009). doi 10.1134/S1990478909010086
O. B. Lupanov, ‘‘On gate and contact-gate circuits,’’ Dokl. Akad. Nauk SSSR 111, 1171–1174 (1956).
E. I. Nechiporuk, ‘‘On the synthesis of gate circuits,’’ Probl. Kibern., No. 11, 37–44 (1963).
I. V. Konoval’tsev, ‘‘On an algorithm for solving linear equations in finite fields,’’ Probl. Kibern., No. 19, 269–274 (1967).
N. Pippenger, ‘‘On the evaluation powers and monomials,’’ SIAM J. Comput. 9, 230–250 (1980). doi 10.1137/0209022
M. I. Grinchuk, ‘‘On computational bit complexity of systems of bilinear forms,’’ in Methods and Systems of Technical Diagnostics. Interuniv. Sb., No. 18 (Saratov Univ., Saratov, 1993), p. 54.
Funding
The work is supported by the Russian Foundation for Basic Research (projects nos. 19-01-00294 and 18-01-00337).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated by E. Oborin
About this article
Cite this article
Gashkov, S.B. A Note on the Fast Computation of Transitive Closure of Graphs and the Multiplication of Integer Matrices. Moscow Univ. Math. Bull. 75, 239–245 (2020). https://doi.org/10.3103/S0027132220060042
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S0027132220060042