Suppose we are processing node X with two children Y and Z (which have already been processed during the post-order traversal). We check the binning strings of Y and Z against that of X. If the binning strings of any child and its parent are different, we have to normalize the dimension of the bins of the child to that of the parent. For a child node with binning string shorter than that of its parent node, we expand the dimension of the bins of the child node by duplicating the corresponding curve for the bins which are added.
After we normalize the dimension of each child node, the curve representing the accumulated cost vs. delay on the parent can be constructed by adding the curves of each child and including the contribution of the module alternative matched at the parent. This must be done for every bin, one at a time. Addition must occur in the common region among all curves to ensure that the resulting merged function reflects feasible matches at the children of n. The curve for successive matchings at the same node n are then merged by applying a lower-bound merge operation on the corresponding curves. Because our decomposed task graph is a DAG instead of a tree, we face the problem of how to pass up the cost of a multiple fanout node to its parents during the post-order traversal. We use a heuristic whereby the cost value of a multiple fanout node is divided by its fanout count when propagated upward in the DAG. This heuristic produces the exact total cost at the root as long as multiple primary outputs are merged into a single root. The proof is straight forward (similar to flow conservation in network flow problem).
The curve addition and merging are performed recursively until the root of the root is reached. The resulting curve is saved in the corresponding bin of the graph at its corresponding node. The set of (t,c) pairs corresponding to the composite curve for the tag at the root node gives the set of all possible arrival time-cost trade-offs for the user to choose from.