Witnesses for Boolean Matrix Multiplication and for Transitive Closure
Witnesses for Boolean Matrix Multiplication and for Transitive Closure
复制标题
布尔矩阵乘法和传递闭包的见证
DOI：
10.1006/jcom.1993.1014
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Oded Margalit
中科院分区：
文献类型：
--
作者：
Z. Galil;Oded Margalit
亚地铁（O（nΩ）的ω<3）算法繁殖布尔材料没有提供证人；即，他们计算C = A·B AIK = BKJ = 1。我们设计了一种确定性算法，用于计算在O（NΩ + ϵ）时间以任何正e为单位的证人的矩阵计算布尔矩阵乘法的证人。
The subcubic (O(nω) for ω < 3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C = A · B but if Cij = 1 they do not find an index k (a witness) such that Aik = Bkj = 1. We design a deterministic algorithm for computing the matrix of witnesses which runs in O(nω + ϵ) time for any positive e. We also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.