A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices. (English. Russian original) Zbl 1465.05177
Mosc. Univ. Math. Bull. 75, No. 6, 239-245 (2020); translation from Vestn. Mosk. Univ., Ser. I 75, No. 6, 14-19 (2020).
Summary: 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.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
| 15B34 | Boolean and Hadamard matrices |
Keywords:
transitive closure of graph; Boolean matrix multiplication; matrix multiplication over rings; bit complexity; Boolean circuits; size and depth; modular addition and multiplicationReferences:
| [1] | Warshall, S., A theorem on Boolean matrices, J. ACM, 9, 11-12 (1962) · Zbl 0118.33104 · doi:10.1145/321105.321107 |
| [2] | Roy, B., Transitive et connexite, C. R. Acad. Sci., 249, 216-218 (1959) · Zbl 0092.15902 |
| [3] | Arlazarov, V. L.; Dinitz, E. A.; Kronrod, M. A.; Faradzhev, I. A., On economical construction of the transitive closure of an oriented graph, Dokl. Akad. Nauk SSSR, 194, 487-488 (1970) · Zbl 0214.23601 |
| [4] | Furman, M. E., 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) |
| [5] | Aho, A.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0326.68005 |
| [6] | Savitch, W. J., Relationship between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci., 4, 177-192 (1970) · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X |
| [7] | Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 554-556 (1969) · Zbl 0185.40101 · doi:10.1007/BF02165411 |
| [8] | 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. doi:10.1109/SWAT.1971.4 |
| [9] | Grinchuk, M. I., Sharpening an upper bound on the adder and comparator depths, J. Appl. Ind. Math., 3, 61-67 (2009) · Zbl 1249.94079 · doi:10.1134/S1990478909010086 |
| [10] | Lupanov, O. B., On gate and contact-gate circuits, Dokl. Akad. Nauk SSSR, 111, 1171-1174 (1956) · Zbl 0072.43204 |
| [11] | E. I. Nechiporuk, ‘‘On the synthesis of gate circuits,’’ Probl. Kibern., No. 11, 37-44 (1963). · Zbl 0166.41905 |
| [12] | I. V. Konoval’tsev, ‘‘On an algorithm for solving linear equations in finite fields,’’ Probl. Kibern., No. 19, 269-274 (1967). · Zbl 0235.65030 |
| [13] | Pippenger, N., On the evaluation powers and monomials, SIAM J. Comput., 9, 230-250 (1980) · Zbl 0447.68035 · doi:10.1137/0209022 |
| [14] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
