TITLE: A Characterization of Networks Supporting Linear Interval Routing AUTHORS: Pierre Fraigniaud and Cyril Gavoille ABSTRACT: Compact routing tables are useful to implement routing algorithms on a distributed memory parallel computer. Interval routing is a popular way of building such compact tables. It was already known that any network can support an interval routing function with only one interval per output port as soon as one allows intervals to be ``cyclic''~\cite{LT87}. However, it might be interesting for practical reasons to allow only the use of ``linear'' intervals (see~\cite{BLT91}). This notion is particularly useful to derive results on networks built by cartesian products (as hypercubes and torus)~\cite{FraGav}. In this paper, we characterize the networks that admit a {\em linear} interval routing function with at most one interval per output port. We also characterize the networks that admit a {\em strict} linear interval routing function with at most one interval per output port.