Transitive Closure and Transitive Reduction

What is the Transitive Closure of a Graph?

Where can I use Transitive Closure?

It is very easy to check if there is a path from a node v to a node w in G using the transitive closure H of a graph G . There is a path in G if and only if there is an edge (v,w) in H.

Transitive Reduction

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 G=(V,E) is a graph H=(V,F) where F is a minimal subset of E such that G and H have the same transitive closure.

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.

Example for transitive closure and transitive reduction

Running Time

See also:

Basic Graph Algorithms

Graphs and Related Data Types

GraphWin for visualizing graphs and graph algorithms

Manual Entries:

Manual Page Basic Graph Algorithms