__Journal article:__

** Maria Luisa Bonet and Samuel R. Buss.
"On the serial transitive closure problem."
**

** 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.