Abstract
In this paper, a fast algorithm is proposed to calculate k(th) power of an n x n Boolean matrix that requires O(kn(3)p) addition operations, where p is the probability that an entry of the matrix is 1. The algorithm generates a single set of inference rules at the beginning. It then selects entries (specified by the same inference rule) from any matrix A(k-1) and adds them up for calculating corresponding entries of A(k). No multiplication operation is required. A modification of the proposed algorithm(1) can compute the diameter of any graph and for a massive random graph, it requires only O(n(2)(1-p)E[q]) operations, where q is the number of attempts required to find the first occurrence of I in a column in a linear search. The performance comparisons say that the proposed algorithms outperform the existing ones.