Seidels sub-cubic algorithm (INCOMPLETE)

Find all the shortest path distances of an adjacency matrix \(A[1..n, 1..n]\), store in \(D[1..n, 1..n]\).

Runtime: \(O(V^{w} log V)\)

\(\omega < 2.373\) is the exponent in the complexity \(O(n^{w})\) for matrix multiplication.

Derivation

Environment

\(MatrixMultiply\): Computes standard product of 2 \(n*n\) matrices in \(O(n^{w})\) time, for some constant \(2 \leq w \le 3\).

Let \(G = (V, E)\), be an undirected, unweighted n-vertex graph.

We represent it using an adjacency matrix: \(A[1..n, 1..n]\).

Steps

  1. If complete graph -> return the original adjacency matrix.

  2. Otherwise compute l2 path matrix, A2 = A * A

  3. To get all paths of length at most 2, \(A2m[i][j] = A[i][j] = 1 \lor A2[i][j] > 0\).

  4. Recurse on A2m

  5. INCOMPLETE