next up previous contents
Next: Non-Deterministic Interval Routing Schemes Up: Variations on the Interval Previous: Fixed and Dynamic Link-Cost   Contents


Hierarchy of the IRS Classes

The strictness of IRS can be obtained by just removing the label $\cL(x)$ from $\cI(x,y)$, and therefore by increasing by one at most its compactness (or linearity compactness). Because a cyclic interval is the union of two linear intervals, we have the trivial collection of inclusions:


\begin{theorem}[Folklore]
For every $k \geqs 1$,
\beginsmall{itemize}
\item $k$-...
...bseteq (k+1)$-$\mbox{$\cS\cL\cI\cR\cS$}_\star$.
\endsmall{itemize}
\end{theorem}

Open question 13    
- Is 1- $\mbox{$\cS\cI\cR\cS$}= 1$- $\mbox{$\cI\cR\cS$}$?
- Same question for k- $\mbox{$\cS\cI\cR\cS$}_d$, k > 1?

In the following, $X \subsetneq Y$ means that $X \subseteq Y$ and $X
\neq Y$. Because in [FJ88] and in [BvLT91] it is shown $K_{2,2k+1} \in (k+1)$- $\mbox{$\cL\cI\cR\cS$}_d$ but not in k- $\mbox{$\cI\cR\cS$}$, we have:


\begin{theorem}[\cite{FJ88}]
For every $k \geqs 1$, $k$-$\mbox{$\cI\cR\cS$}_d \subsetneq (k+1)$-$\mbox{$\cI\cR\cS$}_d$.
\end{theorem}


\begin{theorem}[\cite{BLT91}]
For every $k \geqs 1$,
\beginsmall{itemize}
\item ...
...cR\cS$}_d \subsetneq 1$-$\mbox{$\cI\cR\cS$}_d$.
\endsmall{itemize}
\end{theorem}

Theorem 57, and 58 can be improved by Theorem 47.


\begin{corollary}
For every $k \geqs 1$,
\beginsmall{itemize}
\item $k$-$\mbox{$...
...\cS$}_d \subsetneq k$-$\mbox{$\cI\cR\cS$}_d$.
\endsmall{itemize}
\end{corollary}

From Theorem 47, for every $k \geqs 1$, $K_{2k+1} \in
\floor{(2k+1)/2}$- $\mbox{$\cL\cI\cR\cS$}_d = k$- $\mbox{$\cL\cI\cR\cS$}_d$, and also $K_{2k+1} \in
k$- $\mbox{$\cS\cI\cR\cS$}_d$. From the second point of Theorem 47, $K_{2k+1}
\in t$- $\mbox{$\cS\cL\cI\cR\cS$}_d$ implies that $t \geqs \ceil{(2k+1)/2} = k+1$. Hence $K_{2k+1} \notin k$- $\mbox{$\cS\cL\cI\cR\cS$}_d$. It follows that k- $\mbox{$\cS\cL\cI\cR\cS$}_d \neq
k$- $\mbox{$\cL\cI\cR\cS$}_d$ and k- $\mbox{$\cS\cL\cI\cR\cS$}_d \neq
k$- $\mbox{$\cS\cI\cR\cS$}_d$. Similarly $K_{2k+2} \in k$- $\mbox{$\cI\cR\cS$}$, but $K_{2k+2} \notin k$- $\mbox{$\cL\cI\cR\cS$}_d$, and $K_{2k+2} \notin k$- $\mbox{$\cS\cI\cR\cS$}_d$.




2000-03-21