Short Note: A Note on the Efficiency of an Interval Routing Algorithm

Abstract

An interval routing algorithm for general networks has been proposed separately by Santoro and Khatib and van Leeuwen and Tan. It works optimally for various regular networks, and for the non-regular case it never chooses a route longer than twice the diameter of the network. Van Leeuwen and Tan posed the fundamental question whether there is an optimal interval routing algorithm for any arbitrary network. In this paper we prove the lower-bound result that for certain networks the interval routing algorithm chooses a route which is half as long as the diameter of this network. This answers the question in a negative way.