Premium
A lower bound for interval routing in general networks
Author(s) -
Tse Savio S. H.,
Lau Francis C. M.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199701)29:1<49::aid-net5>3.0.co;2-c
Subject(s) - routing (electronic design automation) , interval (graph theory) , equal cost multi path routing , upper and lower bounds , combinatorics , mathematics , shortest path problem , computer science , graph , interval graph , point (geometry) , static routing , discrete mathematics , pathwidth , routing protocol , computer network , line graph , mathematical analysis , geometry
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 D /4 ‐ 1 lower bound for interval routing in arbitrary graphs, where D is the diameter—i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7 D /4 ‐ 1. © 1997 John Wiley & Sons, Inc.