Article ID: | iaor2002392 |
Country: | United States |
Volume: | 29 |
Issue: | 1 |
Start Page Number: | 49 |
End Page Number: | 53 |
Publication Date: | Jan 1997 |
Journal: | Networks |
Authors: | Tse Savio S.H., Lau Francis C.M. |
Keywords: | communication |
Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7