Technical Report CS0905

Title: The Complexity of the Characterization of Networks Supporting Shortest-Path Interval Routing
Authors: T. Eilam, S. Moran and S. Zaks
Abstract: Interval Routing is a space-efficient routing method for communication networks which has been extensively studied and implemented. Many variants of this basic routing method were proposed, such as Linear Interval Routing, strict Interval Routing and strict Linear Interval Routing. These methods were generalized to allow $k$ intervals per edge. The question of characterizing networks which support {\em optimal} interval routing was thoroughly investigated for each of the variants above, and under different models. Only partial answers, both positive and negative, were given. In this paper we study the characterization of networks which admit optimal (strict or non-strict) interval routing and optimal (strict or non-strict) linear interval routing under the most basic model - the one unit cost, one interval per edge model. We prove that the characterization of these networks is NP-hard. These results significantly extend the related NP-hardness results of \cite{FGS}, and imply that, unless P$=$NP, the results of \cite{BLT91,NS95,ZTRP93}, which gave partial characterizations for some classes of networks which support shortest path interval routing, cannot be pushed further to lead to efficient characterizations for these classes.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion