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.

Back to Sam Buss's publications page.