The name is absent

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, x¹ = v, T = 0, π(T) = 0, σ = { x¹ }, x = æ¹, 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(x^s) for exactly one vertex x^s ψ 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 x^s. 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 σ(x¹ ,π(T)), and
t becomes t ⅛ 1. Set b = b ⅛ 1. Return to Step 1 with x equal to x^t+1.

Step 4. Let, for some к, к <t, x^k be the vertex of σ with label 7r(∕). Then T becomes
T∖{ 7r(∕) }, 7r(T) becomes (7r(l),..., 7r(∕-1)), σ becomes σ(x¹, π(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 Rⁿ⁺¹, i ∈ N.

Table 1. Pivot rules if the vertex x^s of σ(⅛¹,π) is replaced.

<<   6   7   8   9   10   11   12   >>

More intriguing information