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.