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:

- Esko Nuutila, An efficient
transitive closure algorithm for cyclic digraphs,
*Information Processing Letters 52*(1994) 207-213. (596K PostScript file). In this article, I describe a very efficient transitive closure algorithm that is based on strong component detection and compare it to Schmitz's algorithm. - Esko Nuutila and Eljas Soisalon-Soininen, A Single-Pass Algorithm for Transitive Closure, Helsinki University of Technology, Laboratory of Information Processing Science, Technical Report TKO-B95, 1993. (208K PostScript file). A previous version of the algorithm.
- Esko Nuutila and Eljas Soisalon-Soininen, Efficient Transitive Closure Computation, Helsinki University of Technology, Laboratory of Information Processing Science, Technical Report TKO-B113, 1993. (208K PostScript file). Presents another version of the algorithm and the interval representation. Contains interesting test results showing that the interval representation outperforms the traditional representations.
- Esko Nuutila and Eljas Soisalon-Soininen, On finding the strongly connected components in a
directed graph,
*Information Processing Letters 49*(1993) 9-14. (137K PostScript file). In this article, we present improvements on Tarjan's strong component detection algorithm. - Esko Nuutila and Eljas Soisalon-Soininen, On Finding the Strong Components in a Directed Graph, Helsinki University of Technology, Laboratory of Information Processing Science, Technical Report TKO-B94, 1993. (446K PostScript file). A more thorough elaboration on the same subject.
- Esko Nuutila, An experimental study on transitive closure representations, Helsinki University of Technology, Laboratory of Information Processing Science, Technical Report TKO-B134, 1996. (1MB PostScript file).
- Vesa Hirvisalo, Esko Nuutila, Eljas Soisalon-Soininen Transitive closure algorithm DISK_TC and its performance analysis, Helsinki University of Technology, Laboratory of Information Processing Science, Technical Report TKO-B135, 1996. (1.5MB PostScript file). Describes the disk behavior of the algorithm DISK_TC

Back to Esko's homepage.

Last modified: Oct. 9, 1995 enu@cs.hut.fi