next up previous contents
Next: Coding of Interval Routing Up: The Model of Interval Previous: Definition of Interval Routing   Contents


Compactness, Linearity and Strictness of Interval Routing

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, $a,b \leqs 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, $[a,b] = \{ i \mid a \leqs i \leqs b \}$, if $a
\leqs b$, and $[a,b] = \{i \mid b \leqs i \leqs n \} \cup \{i \mid 1\leqs
i \leqs a \}$ otherwise. These two kinds of intervals are respectively called linear and cyclic intervals. For every set $I
\subseteq \{1,\ldots,n\}$, the number of intervals of I is the length, k, of the smallest sequence $(a_1,b_1,\ldots,a_k,b_k)$ such that $I = [a_1,b_1] \cup \ldots \cup [a_k,b_k]$. 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.


\begin{definition}
Let $R = (\cL,\cI)$\ be an IRS on a graph $G$. The {\em comp...
...rcs $(x,y)$\ of $G$, of the
number of intervals of $\cI(x,y)$.
\end{definition}

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 $\cL(x)
\not\in \cI(x,y)$. 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.


next up previous contents
Next: Coding of Interval Routing Up: The Model of Interval Previous: Definition of Interval Routing   Contents

2000-03-21