Linear-Time Algorithms for Dominators and Related Problems (thesis)
This dissertation deals with several topics related to the problem
of finding dominators in flowgraphs. The concept of dominators has
applications in various fields, including program optimization,
circuit testing and theoretical biology. We are interested both in
asymptotically fast algorithms and in algorithms that are
We begin with an experimental study of various algorithms that
compute dominators efficiently in practice. We describe two
practical algorithms that have been proposed in the related
literature: an iterative algorithm initially presented by Allen
and Cocke and later refined by Cooper, Harvey and Kennedy, and the
well-known algorithm of Lengauer and Tarjan. We discuss how to
achieve efficient implementations, and furthermore, introduce a
new practical algorithm. We present a thorough empirical analysis
using real as well as artificial data.
Then we present a linear-time algorithm for dominators
implementable on the pointer machine model of computation.
Previously, Alstrup, Harel, Lauridsen and Thorup gave a
complicated linear-time algorithm for the random-access model.
Buchsbaum, Kaplan, Rogers and Westbrook presented a simpler
dominators algorithm, implementable on a pointer machine and
claimed linear running time. However, as we show, one of their
techniques cannot be applied to the dominators problem and,
consequently, their algorithm does not run in linear time.
Nonetheless, based on this algorithm, we show how to achieve
linear running time on a pointer machine.
Next we address the question of how to verify dominators. We
derive a linear-time verification algorithm, which is much simpler
than the known algorithms that compute dominators in linear time.
Still, this algorithm is non-trivial and we believe it provides
some new intuition and ideas towards a simpler dominators
Finally we study the relation of dominators to spanning trees. Our
central result is a linear-time algorithm that constructs two
spanning trees of any input flowgraph, such that corresponding
paths in the two trees satisfy a vertex-disjointness property we
call ancestor-dominance. This result is related to the concepts of
independent spanning trees and directed st-numberings, previously
studied by various authors, and implies linear-time algorithms for