of σ carry all labels of the set T. Note that every vertex y as a zero-dimensional
simplex { y } is { l(y) }-complete in case l(y) ψ 0.
Now the algorithm generates a sequence of adjacent Nsimplices in A(T) having
Т-complete common facets. Formally the steps of the algorithm can be described
as follows.
Step 0. Set t = 0, x1 = v, T = 0, π(T) = 0, σ = { x1 }, x = æ1, Ri = 0, i = 1, ...,
n ⅛ 1, and b = 1.
Step 1. Calculate l(x) and set L = l(x). If L = 0, an integral point is found and the
algorithm terminates. If L is not an element of T, go to Step 3. Otherwise
L = l(xs) for exactly one vertex xs ψ x of σ.
Step 2. If s = t ⅛ 1 and Rπ(t) = 0, go to Step 4. Otherwise σ and R are adapted
according to Table 1 by replacing xs. Set b = b ⅛ 1. Return to Step 1 with x
equal to the new vertex of σ.
Step 3. If t = n, a completely labeled simplex of type II is found and the algorithm
terminates. Otherwise, a (T ∣J{ L })-complete simplex is found and T be-
comes 7"U{Z}, 7r(T) becomes (π(l),..., 7τ(∕), £), σ becomes σ(x1 ,π(T)), and
t becomes t ⅛ 1. Set b = b ⅛ 1. Return to Step 1 with x equal to xt+1.
Step 4. Let, for some к, к <t, xk be the vertex of σ with label 7r(∕). Then T becomes
T∖{ 7r(∕) }, 7r(T) becomes (7r(l),..., 7r(∕-1)), σ becomes σ(x1, π(T)), t becomes
t — 1, and return to Step 2 with s = к and b = b ⅛ 1.
In Table 1 the vector E(i) denotes the г-th unit vector of Rn+1, i ∈ N.
Table 1. Pivot rules if the vertex xs of σ(⅛1,π) is replaced.