Abstract Generated abstract
This note applies Strassen’s fast matrix multiplication to the computation of the transitive closure of a directed graph. It observes that Boolean matrix multiplication can be carried out by ordinary multiplication of zero one matrices followed by thresholding, giving a bound of order n to the log base 2 of 7 operations. Iterating the update that replaces an adjacency matrix by its Boolean union with its square halves the graph diameter at each step, so at most logarithmically many iterations are needed. The resulting bound for transitive closure is c n to the log base 2 of 7 times log n operations, improving asymptotically on a previously known estimate, although the text notes that practical advantage would require very large n unless matrix multiplication bounds improve.
Full Text
UDC 518.5
MATHEMATICS
M. E. FURMAN
ON THE APPLICATION OF THE METHOD OF FAST MATRIX MULTIPLICATION TO THE PROBLEM OF FINDING THE TRANSITIVE CLOSURE OF A GRAPH
(Presented by Academician I. G. Petrovskii, 10 III 1970)
This algorithm makes it possible to find the transitive closure of a graph in \(cn^{\log_2 7}\lg n\)* operations, which is asymptotically better than the previously known estimate \(cn^3/\lg n\) \((^1)\).
Lemma. Boolean \(n \times n\) matrices can be multiplied in \(cn^{\log_2 7}\) operations.
Indeed, we shall regard these matrices as arithmetic ones consisting of zeros and ones, and multiply them by the method \((^2)\) in \(cn^{\log_2 7}\) operations. Then, in \(cn^2\) operations, we inspect the elements of the product and replace every nonzero element by one. It is obvious that in this way we obtain the Boolean product of the matrices.
Theorem. The transitive closure of a graph of order \(n\) can be obtained in \(cn^{\log_2 7}\lg n\) operations.
Proof. Let \(A_0\) be the adjacency matrix of the given graph. We shall obtain the adjacency matrix of the transitive closure by the following iterations: \(A_{n+1}=A_n \vee A_n^2\).
One iteration requires \(cn^{\log_2 7}\) operations, and the number of iterations required is \(\lg K\), where \(K\) is the maximum distance between two vertices (the diameter of the original graph), since each iteration halves the diameter of the graph. But \(K \le n\); thus, we required fewer than \(cn^{\log_2 7}\lg n\) operations. This method is more advantageous than the method \((^1)\) for values of \(n\) on the order of \(10^{19}\).** However, if better estimates are obtained for the number of operations required for matrix multiplication, then this algorithm will also become advantageous for realistic \(n\).
Moscow State Pedagogical Institute
named after V. I. Lenin
Received
4 III 1970
REFERENCES
\(^1\) V. L. Arlazarov, E. A. Dinitz, M. A. Kronrod, I. A. Faradzhev. DAN, 194, No. 3 (1970).
\(^2\) V. Strassen, Numerische Math., 13, No. 4, 354 (1969).
* \(\lg x\) is the least integer greater than or equal to \(\log_2 x\); \(n\) is the number of vertices of the graph.
** With equal constants entering as factors in the estimate of the number of operations.