The input/output complexity of transitive closure
Jeffrey David Ullman, Mihalis Yannakakis · 1990
Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holding s “values” is available, and that s lies between n, the number of nodes of the graph, and e, the number of arcs. The cost measure we use for algorithms is the I/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.