The algorithm solve_constraints can be modified to deal with non-strict comparisons of the form od(a,b) <<= od(c,d) by, intuitively, marking the edge ab as ``short'' on each iteration if the edge cd has been found to be short.
Specifically, in algorithm solve_constraints, we make the following changes:
H := the connected components of the shorts of Swith the following code:
1. H := the shorts of S; 2. repeat H := the connected components of H; 3. for each weak constraint od(a,b) <<= od(c,d) 4. if cd is in H then add ab to H endif endfor 5. until no change has been made to H in the last iteration.
The proof that the revised algorithm is correct is only a slight extension of the proof of theorem 1 and is given in the appendix.
Optimizing this algorithm for efficiency is a little involved, not only because of the new operations that must be included, but also because there are now four parameters -- n, the number of symbols; e, the number of edges mentioned; s, the number of strict comparison; and w, the number of non-strict comparisons -- and the optimal implementation varies depending on their relative sizes. In particular, either s or w, though not both, may be much smaller than n, and each of these cases requires special treatment for optimal efficiency. The best implementation we have found for the case where both s and w are O(n) has a running time of O(max (n3, nw, s)). The details of the implementation are straightforward and not of sufficient interest to be worth elaborating here.
An immediate consequence of this result is that a couple of problems of inference are easily computed: