TY - GEN
T1 - A fast algorithm to calculate powers of a Boolean matrix for diameter computation of random graphs
AU - Razzaque, Md Abdur
AU - Hong, Choong Seon
AU - Abdullah-Al-Wadud, M.
AU - Chae, Oksam
PY - 2008
Y1 - 2008
N2 - In this paper, a fast algorithm is proposed to calculate k th power of an n×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 can compute the diameter of any graph and for a massive random graph, it requires only O(n2(1-p)E[q]) operations, where q is the number of attempts required to find the first occurrence of 1 in a column in a linear search. The performance comparisons say that the proposed algorithms outperform the existing ones.
AB - In this paper, a fast algorithm is proposed to calculate k th power of an n×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 can compute the diameter of any graph and for a massive random graph, it requires only O(n2(1-p)E[q]) operations, where q is the number of attempts required to find the first occurrence of 1 in a column in a linear search. The performance comparisons say that the proposed algorithms outperform the existing ones.
KW - Adjacency matrix
KW - Boolean matrix
KW - Computational complexity
KW - Graph diameter
KW - Random graphs
UR - https://www.scopus.com/pages/publications/49949097705
U2 - 10.1007/978-3-540-77891-2_6
DO - 10.1007/978-3-540-77891-2_6
M3 - Conference contribution
AN - SCOPUS:49949097705
SN - 354077890X
SN - 9783540778905
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 58
EP - 69
BT - WALCOM
T2 - 2nd International Workshop on Algorithms and Computation, WALCOM 2008
Y2 - 7 February 2008 through 8 February 2008
ER -