connects symbols in two different children of the root. Hence, any instantiation of the tree will make any long edge longer than any short edge.

If no edges are labelled "long" - that is, if H contains the complete graph over the symbols - then there is an inconsistency; all edges are much shorter than the longest edge.

For instance, in table 4, since vw, wx, and xy are all mu smaller than zy, it follows by the triangle inequality that vy is much smaller than zy. But since we also have the constraints that zy is much smaller than vz and that vz is much smaller than vy, we have an inconsistency.

The algorithm then iterates, at the next smaller scale. Since we have now taken care of all the constraints od( a, b ) ≪ od( c, d ), where cd was labelled "long", we can drop all those from S . Let D now be the greatest length of all the edges that remain in S . If a constraint od( a, b ) ≪ od( c, d ) is in the new S , then we know that od( a, b ) is much shorter than D , and we label it "short". We continue as above. The algorithm halts when all the constraints in S have been satisfied, and S is therefore empty; or when we encounter a contradiction, as above.

We now give the formal statement of this algorithm. The algorithm uses an undirected graph over the variable symbols in S .  Given such a graph G , and a constraint C of the form od(a, b) ≪ od(c, d), we will refer to the edge ab as the "short" of C , and to the edge cd as the "long" of C . The shorts of the system S is the set of all shorts of the constraints of S and the longs of S is the set of all the longs of the constraints. An edge may be both a short and a long of S if it appears on one side in one constraint and on the other in another cnstraint.

procedure solve constraints(in S : a system of constraints of the form od(a, b) ≪ od(c, d))
return either a cluster tree T satisfying S if S is consistent; or false if S is inconsistent type: A node N of the cluster tree contains pointers to the parent and children of N ;
the field N label, holding the integer label; and the field N symbols, holding the list of symbols in the leaves of N .

variables: m is an integer; C is a constraint in S ;
H, I are undirected graphs; N, M are nodes of T ;
begin if S contains any constraint of the form, "od(a, b) ~ od(c, c)" then return false; m := the number of variables in S ;
initialize T to consist of a single node N ;
N symbols:= the variables in S; repeat H := the connected components of the shorts of S ;
if H contains all the edges in S then return(false) endif; for each leaf N of T do if not all vertices of N are connected in H then N label := m; for each connected component I of N symbols in H do