Transitive Closure and Transitive Reduction
What is the Transitive Closure of a Graph?The transitive closure of a directed graph
Where can I use Transitive Closure?
It is very easy to check if there is a path from a node
Besides functions to compute the transitive closure of a graph, LEDA
also offers functions to compute the transitive reduction of a graph.
The transitive reduction of a directed graph
Notice that transitive closure and transitive reduction are not exact reversals of each other. If I compute the transitive closure H of a graph G and then compute the transitive reduction G' of H, G' may be a subgraph of G.
Running TimeThe running time for transitive closure and transitive reduction is O(|V||E|).
GraphWin for visualizing graphs and graph algorithms