Abstract: 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.

STNUs have been used for robot control, web-service composition, and business processes.

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 + kn log 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 an improved

algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation.