A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices

DOI10.3103/S0027132220060042zbMath1465.05177OpenAlexW3150371119MaRDI QIDQ2027889

Sergey B. Gashkov

Publication date: 28 May 2021

Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0027132220060042

zbMATH Keywords

Boolean circuitsBoolean matrix multiplicationbit complexitymatrix multiplication over ringsmodular addition and multiplicationsize and depthtransitive closure of graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76) Boolean and Hadamard matrices (15B34) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites Work

• Gaussian elimination is not optimal
• Relationships between nondeterministic and deterministic tape complexities
• On the Evaluation of Powers and Monomials
• A Theorem on Boolean Matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices