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


Characterizations

Every graph supports an IRS: Label arbitrary the nodes and select any routing function with simple paths (without loop) to generate the label of the arcs. Because Interval Routing has been investigated to give compact implementation of routing functions, we are interested to find IRS with small compactness.

Using a depth first search for the labeling of nodes, we have the following result:


\begin{theorem}[\cite{SK85}]
Every acyclic digraph has a $1$-SIRS.
\end{theorem}

Trees have a 1-SIRS (by Theorem 2, and also by Theorem 3 considering undirected trees as acyclic digraphs), and thus, by the use of a spanning tree, every graph has a 1-SIRS. This result has been extended:


\begin{theorem}[\cite{vLT87}]
Every graph has a $1$-SIRS such that all the arcs have non empty
labels.
\end{theorem}

For the latter result, more details can be found in [Tel94, page 136]. A comparison of the labeling of [SK85] and of [vLT87] is presented in [SML94]. However the result does not hold for linear intervals.


\begin{theorem}[\cite{FG98a}]
\mbox{}
\beginsmall{itemize}
\item A graph has a $...
...cted to the same
$2$-edge-connected component. \endsmall{itemize}
\end{theorem}

[FG98] derived an O(n2) time algorithm to label graphs supporting 1-LIRS and 1-SLIRS. A simpler algorithm, based on depth first search, is presented in [EMZ97b]. (The time complexity of the latter is not mentioned.) Note that while theorems above provide characterizations nothing is said about the length of the routing paths.


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

2000-03-21