*For the most recent entries see the
Petri Nets Newsletter.*

## A Simple DFS-Based Algorithm for Linear Interval Routing.

Eilam, T.;
Moran, S.;
Zaks, S.
In:
Mavronicolas, M.; Tsigas, Ph.: *Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany*, pages 37-51.
Springer,
September 1997.

Abstract:
Linear Interval Routing is a space-efficient routing method for
point-to-point communication networks. It is a restricted variant of
Interval Routing where the routing range associated with every link is
represented by an interval with no wrap-around. It was noted by others
that not every network has a valid Linear Interval labeling Scheme (LILS).
A complete characterization of the networks that admit a valid LILS is
known, together with an algorithm that generates a valid LILS in case one
exists. We present a new algorithm that generates an LILS for every
network that admits one. Our algorithm is based on a DFS spanning tree of
the network, and is ``in the spirit'' of the algorithms for Interval
Routing. Our algorithm has few advantages over the earlier algorithm: it
utilizes the well-known theory of DFS spanning trees and is thus simpler
to understand and to implement, it uses all links of the network for
routing (thus it better distributes the load), and it guarantees that some
paths traversed by messages are shortest length paths.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*