Yes, you can imagine a three columns graph, each column has n points. The resultant matrix (AB)_ij= # of path from i-th point in the first column to j-th column in the last column.
Actually, if we assume the Word RAM computational model, the above interpretation leads to an O(n^3/log^2 n) time algorithm, which is better than O(n^3).
No comments:
Post a Comment