Transitive closure

What is transitive closure?

Consider a directed graph G=(V,E), where V is the set of vertices and E is the set of edges. The transitive closure of G is a graph G+ = (V,E+) such that for all v,w in V there is an edge (v,w) in E+ if and only if there is a non-null path from v to w in G.

Why and where is it needed?

Finding the transitive closure of a directed graph is an important problem in many computational tasks. It is required, for instance, in the reachability analysis of transition networks representing distributed and parallel systems and in the construction of parsing automata in compiler construction. Recently, efficient transitive closure computation has been recognized as a significant subproblem in evaluating recursive database queries, since almost all practical recursive queries are transitive.

Despite the increased efficiency of computers the need for faster transitive closure algorithms remains. This is for two reasons. First, the size of the inputs seems to grow in proportion to the growth of the memory capacity. Since the CPU speed has grown at the same rate as the memory capacity, only linear algoritms retain their execution times on typical inputs. Traditional transitive closure algorithms, such as Warshall's algorithm, are not linear. Second, typical inputs (and outputs) in the area of databases do not fit into the main memory. Traditional transitive closure algorithms are mostly designed for main memory operation.

To find out more about transitive closure computation, read my PhD thesis Efficient Transitive Closure Computation in Large Digraphs. In the thesis, I describe the transitive closure problem and other related problems and give an extensive listing of previous transitive closure algorithms and data representations. My main contributions are two new efficient transitive closure algorithms and two new compact transitive closure representations for cyclic digraphs. I show analytically and experimentally that my new algorithm STACK_TC and the so called interval representation are more efficient than previous algorithms and representations.

You can also check the following articles and reports:

Back to Esko's homepage.
Last modified: Oct. 9, 1995