A note on speeding up DC-checking for STNUs

A Simple Temporal Network with Uncertainty (STNU) includes real-valued variables, called time-points; binary difference constraints on those time-points; and contingent links that represent actions with uncertain durations. The most important property of an STNU is called dynamic controllability (DC); and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time-complexity is the RUL$^-$ algorithm due to Cairo, Hunsberger and Rizzi. Its complexity is $O(mn + k^2n + knlog n)$, where $n$ is the number of time-points, $m$ is the number of constraints (equivalently, the number of edges in the STNU graph), and $k$ is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new implementation of the algorithm that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.