RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive
Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 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.

UDC: 519.95


 English version: Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2020, 75:6, 239–245

Bibliographic databases:

© Steklov Math. Inst. of RAS, 2026