** 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:

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:

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.

[FG98] derived an *O*(*n*^{2}) 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:** Efficiency of Interval Routing:
** Up:** The Model of Interval
** Previous:** Coding of Interval Routing
** Contents**

*2000-03-21*