, Assume that d (n ; m)=2. Without loss of generality, we assume that m 1, since otherwise G is simply the complete graph. For each connected component A i , i 2 f 1 : : : m g, w e root a spanning tree T i at any v ertex of A i . L e t n i denote the number of vertices of A i . We n o w construct a shortest path interval routing scheme R = ( L I) o n G. F or i 2 f 1 : : : m g T i , for all j 2 f 1 : : : n i g, G denote the complement graph of G. G is composed of m connected components A 1 : : : A m of order at least two a n d o f d single vertices, vol.1

, For vertices of G with a degree strictly lower than n ; 1, we assign intervals as follows: let i 2 f 1 : : : m g and x be a vertex of A i . For every arc (xx y) o f G

, Hence all vertices of G are labeled and the compactness of R is 1. To prove that R is connected and deene a shortest path routing scheme

Hence either x and y are adjacent or there is a third vertex z of G such that z is connected to both x and y. I f x and y are adjacent, then we h a ve L(y) 2 I (xxy) in both cases (i) and (ii), and by symmetry L(x) 2 I (yyx) ,

Improved routing strategies with succint tables, Journal of Algorithms, vol.11, pp.307-341, 1990. ,

Routing with polynomial communication-space trade-oo, SIAM Journal on Discrete Math, vol.5, issue.2, pp.151-162, 1992. ,

Testing for the consecutive ones property, interval graphs and graphs planarity using pq-tree algorithms, Journal of Computer and System Science, vol.13, pp.335-379, 1976. ,

Linear interval routing, Algorithms Review, vol.2, pp.45-61, 1991. ,

, T9000 et C104 : La nouvelle g en eration de transputers, p.69364

, Lyon Cedex, vol.07, 1993.

A characterisation of networks supporting linear interval routing, 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp.216-224, 1994. ,

Interval routing schemes ,

, , p.69364

, Lyon Cedex, vol.07, 1994.

Optimal interval routing, Parallel Processing: CONPAR '94 -VAPP VI, pp.785-796, 1994. ,

Boolean routing, 7th Int. Workshop on Distributed A lgorithms (WDAG), v olume 725 Lecture Notes in Computer Science, pp.219-233, 1993. ,

Interval labeling schemes for chordal rings, Colloquium on Structural Information and Communication Complexity (SICC), 1994. ,

, STACS'95), 1994.

Designing networks with compact routing tables. Algorithmica, pp.171-190, 1988. ,

Ecient message routing in planar networks, SIAM Journal on Computing, vol.18, issue.4, pp.843-857, 1989. ,

Space-eecient message routing in cdecomposable networks, 164{181, F ebruary, vol.19, 1990. ,

DOI : 10.1137/0219011

URL : https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1532&context=cstech

, Private communications in, 1994.

Lower bounds on interval routing, 1994. ,

Computers and Intractability -A Guide to the Theory of NP-Completeness, 1977. ,

, Graph Theory, 1969.

On multi-label linear interval routing schemes, 19th International Workshop on Graph -Theoretic Concepts in Computer Science -Distributed A lgorithms (WG), v olume 790 of Lecture Notes in Computer Science, pp.338-349, 1993. ,

The Theory of ErrorCorrecting Codes, 1977. ,

Networks, routers and transputers: Function, perfomance, and applications, 1993. ,

A trade-oo between space and eeciency for routing tables, 20th Annual ACM Symposium on Theory of Computing (STOC), pp.43-52, 1988. ,

DOI : 10.1145/65950.65953

On eecient o f i n terval routing algorithms, Mathematical Foundations of Computer Science (MFSC), vol.324, pp.492-500, 1988. ,

Labelling and implicit routing in networks, The Computer Journal, vol.28, issue.1, pp.5-8, 1985. ,

DOI : 10.1093/comjnl/28.1.5

URL : https://academic.oup.com/comjnl/article-pdf/28/1/5/1268471/280005.pdf

Interval routing, The Computer Journal, vol.30, issue.4, pp.298-307, 1987. ,