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.
This PDF file was generated by transforming the original EPS files to PDF and changing the epsfbox commands to includegraphics commands and then running pdflatex. I had to do add some vskips to various points of the latex input to get the same page breaks as in the original printed version. If you find out any problems, pleas let me know. Back to Esko's homepage.