Pre-order traversal begins at the root of the decomposed task graph and proceeds toward the leaves. Consider a node X of the graph. The (output) arrival time and the type constraint for the node are known. Our task is to determine the arrival times and the type constraints for each of its child nodes.
Consider a child Z of node X. We are assured that at least one of the tagged curves of X is consistent with the type constraint passed down to X. If there is exactly one such curve stored at X, we pick the minimum-cost point of the curve which satisfies the arrival time constraint of X. Otherwise, there are more than one tagged curves that are consistent with the type constraints passed down to node X. In this case, we find the corresponding best cost point on each curve (which satisfies the timing constraint) and among them pick the solution which has the overall minimum-cost. Next, we update the type constraint for node Z as the Union of type constraint passed down to node X and the constraint implied by the tag of the chosen point on the tagged curve (or bin) and set the timing constraint of Z as the timing constraint at X minus the delay of the match at X.
A multiple-fanout node is visited multiple times during the pre-order traversal. During each visit, the arrival time and possibly type constraint of the node may change to guarantee that arrival time and type consistency constraints for all paths emanating from that node toward the root of the graph are satisfied. Due to the introduction of a single root during the binning string computation, we do not encounter conflicting type consistency constraints from different fanout branches of such a node.
Theorem:
Dynamic programming with binning solves Problem 
optimally while satisfying the type consistency constraints.