Journal article:
Maria Luisa Bonet and Samuel R. Buss.
"On the serial transitive closure problem."
SIAM Journal on Computing 24 (1995) 109-122.
Download article: postscript or PDF.
Abstract: The serial transitive closure problem is the problem of, 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. We give a nearly linear upper bound on the number of steps in optimal solutions to the serial transitive closure problem for the case of graphs which 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.
Related paper: The deduction rule and linear and near-linear proof simulations, in JSL 1993.
Earlier conference paper: On the deduction rule and the number of proof lines, in LICS'91.