The Serial Transitive Closure Problem for Trees
Marı́a Luisa Bonet, Samuel R. Buss · SIAM Journal on Computing · 1995
The serial transitive closure problem is the problem, given a directed graph G and a list of edges, called closure edges, which are in the transitive closure of the graph, to generate all the closure edges from edges in G. A nearly linear upper bound is given on the number of steps in optimal solutions to the serial transitive closure problem for the case of graphs that are trees. “Nearly linear” means $O(n \cdot \alpha (n))$, where $\alpha $ is the inverse Ackermann function. This upper bound is optimal to within a constant factor.