next up previous contents
Next: Hierarchy of the IRS Up: Variations on the Interval Previous: Variations on the Interval   Contents


Fixed and Dynamic Link-Cost Models

In [FJ88] the first results dealing with weighted graphs and dynamic link-cost model are presented. Their nice characterization for compactness 1 has been extended in [BvLT91] for the linear case, and finally [BLTT97] proved that a linear time algorithm exists for the characterization of graphs of compactness k, for every fixed $k \geqs 1$, in the setting of dynamic link-cost model.

In this paragraph we consider weighted graphs, that is a pair (G,w) where G=(V,E) is a graph, and w a non negative function that assigns a ``weight'' for each edge (the weight is the same for $(x,y)
\in E$ and $(y,x) \in E$). This weight can take into account the communication costs along the link between x and its neighbor y. The cost of a path in a weighted graph is the sum of the weights of the arcs that compose the path. A minimum path is a path of minimum cost between its two end-points.


\begin{definition}
A graph $G$\ supports a {\em minimum fixed cost} IRS if for ...
...um fixed cost $k$-IRS is denoted by $k$-$\mbox{$\cI\cR\cS$}_f$.
\end{definition}

Let us denote by k- $\mbox{$\cI\cR\cS$}$ the class of graphs which support a shortest path k-IRS. Clearly k- $\mbox{$\cI\cR\cS$}_f \subseteq k$- $\mbox{$\cI\cR\cS$}$ because the uniform weight function is a particular case of the model k- $\mbox{$\cI\cR\cS$}$.

Another model assumes that the addresses of the nodes are fixed once in advance (independently of the link-costs), and then the weights can change. This model takes into account the situation where the link-costs evolve over time, and where the computation of the node-labeling through the network is impossible, whereas the edge-labeling remains locally adjustable in order to achieve a routing path of minimal length.


\begin{definition}
A graph $G$\ supports a {\em minimum dynamic cost} IRS if th...
... dynamic cost $k$-IRS is denoted by $k$-$\mbox{$\cI\cR\cS$}_d$.
\end{definition}

Similarly, k- $\mbox{$\cI\cR\cS$}_f \subseteq k$- $\mbox{$\cI\cR\cS$}$ because for $G \in
k$- $\mbox{$\cI\cR\cS$}$, the node-labeling $\cL$ gives a labeling solution for every weight function w. Hence k- $\mbox{$\cI\cR\cS$}_f \subseteq k$- $\mbox{$\cI\cR\cS$}_f \subseteq k$- $\mbox{$\cI\cR\cS$}$, and all the lower bounds proved in the uniform link-cost model hold also for the two other models. We extend the previous notation to the linear and/to strict IRS in a similar way.

The dynamic link-cost model assumes implicitly that addresses of the nodes cannot be permuted in order to optimize the number of intervals per edge with the routing path lengths. It turns out that Theorem 15 (compactness at most n/4+o(n) for every graph) holds for the fixed link-cost model, but not for the dynamic link-cost model.

For convenience, a statement which holds independently for all the classes k- $\mbox{$\cI\cR\cS$}$, k- $\mbox{$\cI\cR\cS$}$, and k- $\mbox{$\cI\cR\cS$}$ is termed with k- $\mbox{$\cI\cR\cS$}_{\star}$. By definition, we set $K_1 \in
0$- $\mbox{$\cS\cL\cI\cR\cS$}_\star$.


\begin{theorem}\mbox{}
\beginsmall{itemize}
\item For every $n$-node graph $G$, ...
...lies $k \geqs \ceil{n/2}-1$.
\endsmall{itemize}
\endsmall{itemize}
\end{theorem}

Let us start to prove the first point. Let $R=(\cL,\cI)$ be an IRS on G. Consider $I = \cI(x,y) \subseteq \{1,\ldots,n\}$. Let k be the number of intervals of I. Let $I' = \{1,\ldots,n\}-I$ be the complement of I, and k' its number of intervals. Clearly, $k+k'
\leqs n$. Moreover, for the linear cases $k \leqs k'+1$, and k=k' for cyclic intervals. It implies that

\begin{displaymath}
2k \leqs k+k'+1 \leqs n+1 \quad\Rightarrow\quad k \leqs \floor{\frac{n+1}{2}}
= \ceil{\frac{n}{2}},
\end{displaymath}

for the linear cases, and $2k = k+k' \leqs n$ which implies $k \leqs
\floor{n/2}$ for the cyclic cases. It remains to show the non-strict cases.

Assume R is non-strict and k is minimum. To show that $G \in
\floor{n/2}$- $\mbox{$\cL\cI\cR\cS$}_\star$, it suffices to show that for n odd the previous bound decreases by 1. Assume n=2i+1, and that I is composed of $\ceil{n/2} = i+1$ intervals. Note that I' is necessarily composed of at least i intervals. Moreover all the intervals that composed I and I' are single, i.e., of the form [a]. Indeed if 1 interval (at least) is composed of 2 integers (or more) then the number of elements in $I \cup I'$ would be (i+1)+i+1 = 2i+2=n+1 which is impossible. If $\cL(x) \in I$ then $\cL(x)$ appears as a single interval, so removing it will save one interval. I contains 1 and n, because I and I' are composed of single intervals only, and |I| > |I'|. If $\cL(x) \notin I$ then its insertion will win one interval because $\cL(x)-1$ and $\cL(x)+1$ are both single intervals and both belong to I (we can assume $n \geqs 3$ because for $n \leqs 2$ the result is trivial).

To prove $G \in (\ceil{n/2}\!-\!1)$- $\mbox{$\cI\cR\cS$}_{\star}$ it suffices to prove it for n even. So assume n=2i, and I composed of $\floor{n/2}=i$ intervals. Similarly I and I' are composed of single intervals only, and thus the insertion or deleting of $\cL(x)$ in I will decreases by 1 the number of intervals of I.

Let us show the second point. Consider the nodes labeled 1 and 2. First consider the case of strict intervals ( $\mbox{$\cS\cL\cI\cR\cS$}_d$ or $\mbox{$\cS\cI\cR\cS$}_d$). Choose w such that w(2,1)=1, w(1,2i+1)=1 for i integer such that $3 \leqs 2i+1 \leqs n$, and w(x,y)=3 otherwise. The shortest paths from 2 to i travels to 1 if i is odd (cost $\leqs 2$, and 3 otherwise). Thus $\cI(2,1)=\{1,3,\ldots,2i+1,\ldots\}$. It is composed of $\vert\cI(2,1)\vert = \ceil{n/2}$ linear intervals (there are no consecutive integers in $\cI(2,1)$), and $\floor{n/2}$ cyclic intervals (in the odd case 1 and n can be merged).

For the non-strict intervals ( $\mbox{$\cL\cI\cR\cS$}_d$ or $\mbox{$\cI\cR\cS$}$), choose w such that w(2,1)=1, w(1,2i)=1 for i integer such that $4 \leqs 2i
\leqs n$, and w(x,y)=3 otherwise. The shortest paths from 2 to i travels to 1 if i is even ($i \neq 2$). Hence $\cI(2,1) \subseteq
\{1,4,\ldots,2i,\ldots\}$. $\cL(2)$ can belong to $\cI(2,1)$ or not, it does not change the number of intervals of $\cI(2,1)$. It is composed of $\vert\cI(2,1)\vert = \floor{n/2}$ linear intervals, and $\floor{(n-1)/2} = \ceil{n/2}-1$ cyclic intervals. This completes the proof.

The inherent definition of the link-cost model imposes that a graph can have very different compactness depending on the model (uniform, fixed or dynamic link-cost). Indeed we have seen in Theorem 20 that $K_n \in 1$- $\mbox{$\cS\cL\cI\cR\cS$}_d$. In the opposite to the class k- $\mbox{$\cI\cR\cS$}$ the fixed and dynamic link-cost models have known characterizations.

The definition of outerplanar graphs is recalled in Paragraph 3.4.


\begin{theorem}[\cite{FJ88}]
$G \in 1$-$\mbox{$\cS\cI\cR\cS$}_d$\ if and only if $G$\ is outerplanar.
\end{theorem}


\begin{theorem}[\cite{BLT91}]
$G \in 1$-$\mbox{$\cI\cR\cS$}_d$\ if and only if ...
...$-vertex-con\-nect\-ed
component of $G$\ is outerplanar or $K_4$.
\end{theorem}

A G-star is a graph obtained from G by adding zero or more nodes of degree one to the nodes of G. A centipede is a P-star, P being a path where some edges of P are replaced by a K3 (the edge of the path is identified to an edge of K3). A Y-graph is a tree on 7 nodes with one node of degree 3, and three nodes of degree 2. Finally, H is a subgraph of minimum paths of a weighted graph G if H is a subgraph of G, and if for all $x,y \in V(H)$, all the minimum paths between x and y in G are wholly contained in H. For unweighted graph G, H is called subgraph of shortest paths.


\begin{theorem}[\cite{BLT91}]\mbox{}
\beginsmall{itemize}
\item $G \in 1$-$\mbox...
...cR\cS$}_d$\ if and only if $G$\ is a centipede.
\endsmall{itemize}
\end{theorem}

According to [vLT94] we have:


\begin{theorem}[\cite{BLT94}]
$G \in 1$-$\mbox{$\cS\cL\cI\cR\cS$}_d$\ if and only if $G$\ is a path.
\end{theorem}

The following result proposes a tool to show that a given graph does have not compactness k. It suffices to show that one of its subgraphs of minimum paths is not.


\begin{theorem}[\cite{FG98a}]
A given graph belongs to $k$-$\mbox{$\cI\cR\cS$}_...
...}_\star$\ (the same holds for the
linear and/or strict variants).
\end{theorem}

This is also a sufficient condition since G is a subgraph of minimum paths of itself. In the original paper, the result has been mentioned only for the uniform link-cost model. The proof holds for all the models, and can be easily adapted for a version using stretch factor and dilation.

An interesting application of Theorem 52, and the lithium based characterization of 1-linear IRS (cf. Theorem 5) is that every graph that contains a weak-lithium graph, e.g., K1,3, as subgraph of shortest paths does not support any shortest path 1-SLIRS.

Because IRS (with cyclic intervals) are invariant under shifting of the labels modulo n, it is easy to compose graph by union sharing one cut-vertex. The sufficient condition of the next result is an application of Theorem 52.


\begin{theorem}[\cite{GG98}]
For every $k \geqs 1$, $G \in k$-$\mbox{$\cI\cR\cS...
...ox{$\cI\cR\cS$}_\star$\ (\resp $k$-$\mbox{$\cS\cI\cR\cS$}_\star$).
\end{theorem}

Here a version for the linear case, and for k=1:
\begin{theorem}[\cite{NS96}]
Let $G$\ be a graph, let $G_1, \ldots,G_t$\ be its...
...nd $x_{i,i+1}$\ has label
$\vert V(G_i)\vert$. \endsmall{itemize}
\end{theorem}

The next result establishes an interesting bridge between minor-taking theory and minimum dynamic cost IRS.


\begin{theorem}[\cite{BLTT97}]
For each $k \geqs 1$,
\beginsmall{itemize}
\item...
...ost $2k+3$\ (the same holds for its variants).
\endsmall{itemize}
\end{theorem}

The two last results of Theorem 55 implies that the class k- $\mbox{$\cI\cR\cS$}$ covers a small part of all the graphs since almost all graphs (even sparse) have a treewidth $\Theta(n)$, see [Klo94, Theorem 5.3.2, page 58]. Note that the converse is false because Theorem 34 shows that there are graphs of treewidth bounded by k which have unbounded compactness for the uniform link-cost model, hence for all the models.

Open question 12    
- For $G \in
k$- $\mbox{$\cI\cR\cS$}$, what is the complexity of finding the node-labeling $\cL$ of G?


next up previous contents
Next: Hierarchy of the IRS Up: Variations on the Interval Previous: Variations on the Interval   Contents

2000-03-21