COMPUTE (x,y) {
if(matrix[x][y] != EMPTY) return matrix[x][y];
for all k in 1:N
if(COMPUTE(x,k)&&COMPUTE(k,y)) matrix[x][y]=matrix[y][x]=1; EXIT
endfor
matrix[x][y]=0;
}
CLOSURE (M){ //M is the matrix
for all i,j s.t matrix[x][y]=EMPTY
COMPUTE[i][j]
endfor
}
// M is now the closure.
CLAIM : For every possible edge in the complete graph only one operation is
done effectively.
So this is O(n^2).
Can anyone validate/disprove the claim.?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
