We present the first implementations of certified algorithms for computing dominators, and exhibit their efficiency experimentally on graphs taken from a variety of applications areas. The certified algorithms are obtained by augmenting dominator-finding algorithms to compute a certificate of correctness that is easy to verify. A suitable certificate for dominators is obtained from the concepts of low-high orders and independent spanning trees. Therefore, our implementations provide efficient constructions of these concepts as well, which are interesting in their own right. Furthermore, we present an experimental study of efficient algorithms for computing dominators on large graphs.
展开▼
