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