The notion of compactness and linearity are related to the way of
coding the labels of the arcs, whereas strictness is related to the
construction of the IRS itself. For integers n, ,
an
interval [a,b] with respect to n is the set of consecutive
integers between a and b, n and 1 being considered as
consecutive. Formally,
,
if
,
and
otherwise. These two kinds of intervals are respectively
called linear and cyclic intervals. For every set
,
the number of intervals of I is
the length, k, of the smallest sequence
such that
.
The number of
linear intervals of I is defined similarly, but all intervals must
be linear. The number of intervals of the empty set is 0.
The linear compactness is defined similarly from the number of linear
intervals of the arc-labels. Compactness and linear compactness differ
by at most 1: every cyclic interval equals two linear intervals. We
denote by k-IRS every IRS of compactness k. A k-IRS that has
also a linear compactness k is called a k-Linear Interval Routing
Scheme (k-LIRS for short). Moreover, an IRS is qualified as strict, denoted by SIRS, if every arc (x,y) satisfies
.
Hence we have four variants for IRS depending on
linearity and strictness: k-IRS, k-LIRS, k-SIRS, and k-SLIRS.
Section 4.2 gives more details about the hierarchy of
the classes induced by these different IRS.
The IRS depicted in Figure 1 is linear, non-strict, and of linear compactness 1. So this is a 1-LIRS.