Question:
Transitive closure:
In class we saw how to compute the transitive closure of a graph
in O(n^3) time.
(Given the adjacency matrix, we created an array so that entry (i,j) is
non-zero if there is a path from vertex i to vertex j).
Here we'll see a better way.
Assume we have the following routines:
void DisassembleMatrix(int E[][], int *(A[][]), int *(B[][]),
int *(C[][]), int *(D[][]), int n); // O(n^2) time
int[][] AssembleMatrix(int A[][], int B[][], int C[][], int D[][]);
// O(n^2) time
int[][] MatrixCopy(int A[][], int n); // O(n^2) time
void MatrixMultiply(int dest[][], int src[][], int n); // O(n^2.81) time
void MatrixAdd(int dest[][], int src[][], int n); // O(n^2) time
Then the following will compute the transitive closure.
int[][]
TransitiveClosure(int E[][], int n) {
// divide matrix into four n/2 x n/2 submatrices
// [ A B ]
// E = [ ]
// [ C D ]
DisassembleMatrix(E, &A, &B, &C, &D, n);
// compute Dt
Dt = TransitiveClosure(D, n / 2);
// compute F = A + B * Dt * C
F = MatrixCopy(B, n / 2);
MatrixMultiply(F, Dt, n / 2);
MatrixMultiply(F, C, n / 2);
MatrixAdd(F, A, n / 2);
// compute Ft
Ft = TransitiveClosure(F, n / 2);
// [ Ft Ft * B * Dt ]
// return [ ]
// [ Dt * C * Ft Dt + Dt * C * Ft * B * Dt ]
// compute Dt * C * Ft
lowerleft = MatrixCopy(Dt, n / 2);
MatrixMultiply(lowerleft, C, n / 2);
MatrixMultiply(lowerleft, Ft, n / 2);
// compute Dt + Dt * C * Ft * B * Dt
lowerright = MatrixCopy(lowerleft, n / 2);
MatrixMultiply(lowerright, B, n / 2);
MatrixMultiply(lowerright, Dt, n / 2);
MatrixAdd(lowerright, Dt, n / 2);
// compute Ft * B * Dt
upperright = MatrixCopy(Ft, n / 2);
MatrixMultiply(upperright, B, n / 2);
MatrixMultiply(upperright, Dt, n / 2);
return ReassembleMatrix(Ft, upperright, lowerleft, lowerright, n);
}
Write a recurrence for how long it takes to compute the transitive
closure for a graph of n vertices, and solve the recurrence
using big-O notation.
Answer: The recurrence is
T(n) = T(n / 2) + O(n^2.81)The solution is T(n) = O(n^2.81).