A linear-time algorithm is presented for finding dominators in control flow graphs.

In the first part of the paper we show how to extend recent methods for solving a special case of the union-find problem in linear time, to a special case of the eval-link-update problem for computing the minimum function defined on paths of trees. In the cases where our approach is applicable, we give a way to perform m eval, link, and update operations on n elements in O(m + n) time and O(n) space, improved from O(m α(m + n, n) + n) time and O(n) space in the more general case, where α is a functional inverse of Ackermans function. The technique gives similar improvements in the efficiency of algorithms for solving several network optimization problems in the case where all the keys involved are integers in some suitable range. In the second part of the paper we show how to use the new technique for speeding up the fastest known algorithm for finding dominators in flow graphs so that it runs in linear time. We introduce the notions of pseudo and external dominators which are both computable in linear time and make the technique introduced in the first part applicable for finding immediate dominators. We first give an algorithm for a limited class of graphs which include cycle free graphs, and thus can be used to find dominators in reducible flow graphs. We then show how to extend our technique for computing dominators on any flow graph. All the algorithms we describe run on a Random Access Machine.

We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We show that any pointer machine that solves this problem requires $\Omega (\log \log n)$ time per query in the worst case, where n is the total number of vertices in the trees. On the other hand, we present an algorithm for a random access machine with uniform cost measure (and a bound of $\Omega (\log n)$ on the number of bits per word) that requires $O(1)$ time per query and $O(n)$ preprocessing time, assuming that the collection of trees is static. For a version of the problem in which the trees can change between queries, we obtain an almost-linear-time (and linear-space) algorithm.

We investigate two lowest common ancestor (LCA) problems on trees. We give a linear time algorithm for the off-line problem, on a random access machine (RAM). The half-line problem is one in which LCA queries on a fixed tree are arriving on line. We extend our RAM algorithm to answer each individual query in 0(1) time, with 0(n) preprocessing time. Tarjan observed that this result helps to explicate the difference in power between RAM and pointer machines. We also show how to modify our algorithm to achieve a linear preprocessing time, optimal query time, algorithm on a reference machine.