  We introduce new algorithms for computing non-termination sensitive control
dependence (NTSCD) and decisive order dependence (DOD). These relations on
control flow graph vertices have many applications including program slicing
and compiler optimizations. Our algorithms are asymptotically faster than the
current algorithms. We also show that the original algorithms for computing
NTSCD and DOD may produce incorrect results. We implemented the new as well as
fixed versions of the original algorithms for the computation of NTSCD and DOD
and we experimentally compare their performance and outcome. Our algorithms
dramatically outperform the original ones.
