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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.