  The problem of finding dominators in a directed graph has many important
applications, notably in global optimization of computer code. Although linear
and near-linear-time algorithms exist, they use sophisticated data structures.
We develop an algorithm for finding dominators that uses only a "static tree"
disjoint set data structure in addition to simple lists and maps. The algorithm
runs in near-linear or linear time, depending on the implementation of the
disjoint set data structure. We give several versions of the algorithm,
including one that computes loop nesting information (needed in many kinds of
global code optimization) and that can be made self-certifying, so that the
correctness of the computed dominators is very easy to verify.
