Transitive reduction
How to calculate a transitive reduction of a graph G.
Let Gtr is a transitive reduction of graph G.
Let Gtc is a transitive closure of graph G.
1. Build an adjacency matrix of G. Calculate an adjacency matrix for Gtc using DFS on G.
2. Ok, now we have G and its transitive closure Gtc. The resulting Gtr can be obtained use the following formula: Gtr = G - (G x Gtc).
We have 2 steps here:
1. The first step takes n*n operations (DFS). So, O(n*n)
2. The matrix substitution takes O(n*n) time. The rough matrix multiplication takes O(n*n*n). Though on cuda, if we load n*n threads, it leads to O(n).
So, the most computative operation here is a matrix multiplication.
Let Gtr is a transitive reduction of graph G.
Let Gtc is a transitive closure of graph G.
1. Build an adjacency matrix of G. Calculate an adjacency matrix for Gtc using DFS on G.
2. Ok, now we have G and its transitive closure Gtc. The resulting Gtr can be obtained use the following formula: Gtr = G - (G x Gtc).
We have 2 steps here:
1. The first step takes n*n operations (DFS). So, O(n*n)
2. The matrix substitution takes O(n*n) time. The rough matrix multiplication takes O(n*n*n). Though on cuda, if we load n*n threads, it leads to O(n).
So, the most computative operation here is a matrix multiplication.
Comments