|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2020, Number 6, Pages 14–19
(Mi vmumm4360)
|
|
|
|
Mathematics
A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices
S. B. Gashkov Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
Some algorithms for transitive closure and Boolean matrix multiplication are compared. The bounds for size and depth of corresponding boolean circuits are given.
Key words:
transitive closure of graph, boolean matrix multiplication, matrix multiplication over rings, bit complexity, boolean circuits, size and depth, modular addition and multiplication.
Citation:
S. B. Gashkov, “A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2020, no. 6, 14–19; Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 75:6 (2020), 239–245
Linking options:
https://www.mathnet.ru/eng/vmumm4360 https://www.mathnet.ru/eng/vmumm/y2020/i6/p14
|
|