, 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

. =-k-n, 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)

A. Baruch-a-w-erbuch, N. Bar-noy, D. Linial, and . Peleg, Improved routing strategies with succint tables, Journal of Algorithms, vol.11, pp.307-341, 1990.

A. Baruch, D. Erbuch, and . Peleg, Routing with polynomial communication-space trade-oo, SIAM Journal on Discrete Math, vol.5, issue.2, pp.151-162, 1992.

S. Kellogg, G. S. Booth, and . Lueker, 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.

E. M. Bakker, J. Van-leeuwen, and R. B. Tan, 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.

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

P. Fraigniaud and C. Gavoille, Interval routing schemes

. Lyon, , p.69364

, Lyon Cedex, vol.07, 1994.

P. Fraigniaud and C. Gavoille, Optimal interval routing, Parallel Processing: CONPAR '94 -VAPP VI, pp.785-796, 1994.

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

M. Flammini, G. Gambosi, and S. Salomone, Interval labeling schemes for chordal rings, Colloquium on Structural Information and Communication Complexity (SICC), 1994.

M. Flammini, G. Gambosi, and S. Salomone, STACS'95), 1994.

G. N. Frederickson and R. Janardan, Designing networks with compact routing tables. Algorithmica, pp.171-190, 1988.

G. N. Frederickson and R. Janardan, Ecient message routing in planar networks, SIAM Journal on Computing, vol.18, issue.4, pp.843-857, 1989.

G. N. Frederickson and R. Janardan, 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

M. Flammini, Private communications in, 1994.

M. Flammini, J. Van-leeuwen, and A. Marchetti-spaccamela, Lower bounds on interval routing, 1994.

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability -A Guide to the Theory of NP-Completeness, 1977.

F. Harary, Graph Theory, 1969.

E. Kranakis, D. Krizanc, and S. S. Ravi, 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.

J. Florence, N. Macwilliams, and . Sloane, The Theory of ErrorCorrecting Codes, 1977.

M. D. May, P. W. Thompson, and P. H. Welch, Networks, routers and transputers: Function, perfomance, and applications, 1993.

D. Peleg and E. Upfal, 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

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

N. Santoro and R. Khatib, 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

J. Van-leeuwen and R. B. Tan, Interval routing, The Computer Journal, vol.30, issue.4, pp.298-307, 1987.