Nuutila, E., Efficient Transitive Closure Computation in Large Digraphs. Acta Polytechnica Scandinavica, Mathematics and Computing in Engineering Series No. 74, Helsinki 1995, 124 pages. Published by the Finnish Academy of Technology. ISBN 951-666-451-2, ISSN 1237-2404, UDC 681.3.

Abstact

This thesis examines new efficient transitive closure algorithms and representations. Two new transitive closure algorithms that are based on detecting the strong components are presented. Worst-case analysis and simulation experiments show that the new algorithms are more efficient than the previous algorithms that are based on strong component detection. The algorithms use Tarjan's algorithm for strong component detection. Also, two improved versions of Tarjan's algorithm are presented.

Two new compact transitive closure representations are presented. The first representation is based on intervals of consecutively numbered strong components. The representation generalizes a previous method for compressing the transitive closure of an acyclic graph. The new representation also handles cyclic graphs, and it can be computed more efficiently than the previous representation. The second new representation generalizes the chain decomposition representation for acyclic graphs to handle cyclic graphs.

Simulation experiments show that the interval representation is superior to the commonly used adjacency list representation. The experiments indicate that the interval representation requires typically at most a space linear to the number of vertices in the input graph. The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.


Back to Esko's homepage.
Last modified: Oct. 9, 1995
enu@cs.hut.fi