{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:53:46Z","timestamp":1747810426721},"reference-count":84,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4733,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1016\/s0304-3975(99)00283-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T14:10:41Z","timestamp":1027606241000},"page":"217-253","source":"Crossref","is-referenced-by-count":50,"title":["A survey on interval routing"],"prefix":"10.1016","volume":"245","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00283-2_BIB1","first-page":"45","article-title":"Linear interval routing","volume":"2","author":"Bakker","year":"1991","journal-title":"Algorithms Rev."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB2","unstructured":"E.M. Bakker, J. van Leeuwen, R.B. Tan, Unpublished manuscript, 1994."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jpdc.1995.1002","article-title":"Distributed loop computer networks: a survey","volume":"24","author":"Bermond","year":"1995","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB4","unstructured":"H.L. Bodlaender, A tourist guide through treewidth, Technical Report RUU-CS-92-12, Utrecht University, March 1992, Revised March 1993."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB5","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1006\/inco.1997.2669","article-title":"On interval routing schemes and treewidth","volume":"139","author":"Bodlaender","year":"1997","journal-title":"Inform. Comput."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB6","unstructured":"V. Braume, Theoretische und experimentelle Analyse von Intervall-Routing Algorithmen, Ph.D. Thesis, Department of Mathematics and Computer Science, University of Paderborn, 1993."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB7","doi-asserted-by":"crossref","unstructured":"H. Buhrman, J.-H. Hoepman, P. Vit\u00e1nyi, Optimal routing tables, in: 15th Ann. ACM Symp. on Principles of Distributed Computing (PODC), ACM Press, New York, May, 1996, pp. 134\u2013142.","DOI":"10.1145\/248052.248076"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB8","doi-asserted-by":"crossref","unstructured":"S. Cicerone, G. Di Stefano, M. Flammini, Static and dynamic low congested interval routing schemes, in: K.G. Larsen, S. Skyum, G. Winskel (Eds.), 25th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 1443, Springer, Berlin, July 1998, pp. 592\u2013603.","DOI":"10.1007\/BFb0055087"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB9","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TC.1987.1676939","article-title":"Deadlock-free message routing in multiprocessor interconnection networks","volume":"C-36","author":"Dally","year":"1987","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB10","unstructured":"P. de la Torre, L. Narayanan, D. Peleg, Thy neighbor's interval is greener: a proposal for exploiting interval routing schemes, in: 5th Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton Scientific, 1998."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB11","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","article-title":"Topology of series parallel graphs","volume":"10","author":"Duffin","year":"1965","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB12","doi-asserted-by":"crossref","unstructured":"T. Eilam, C. Gavoille, D. Peleg, Compact routing schemes with low stretch factor, in: 17th Ann. ACM Symp. on Principles of Distributed Computing (PODC), ACM PRESS, New York, August 1998, pp. 11\u201320.","DOI":"10.1145\/277697.277702"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB13","doi-asserted-by":"crossref","unstructured":"T. Eilam, S. Moran, S. Zaks, A lower bound for linear interval routing, in: \u00d6. Babao\u011flu, K. Marzullo (Eds.), 10th Internat. Workshop on Distributed Algorithms (WDAG), Lecture Notes in Computer Science, vol. 1151, Springer, Berlin, October 1996, pp. 191\u2013205.","DOI":"10.1007\/3-540-61769-8_13"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB14","unstructured":"T. Eilam, S. Moran, S. Zaks, The complexity of the characterization of networks supporting shortest-path interval routing, in: D. Krizanc, P. Widmayer (Eds.), 4th Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton Scientific, July 1997, pp. 99\u2013111."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB15","doi-asserted-by":"crossref","unstructured":"T. Eilam, S. Moran, S. Zaks, A simple DFS-based algorithm for linear interval routing, in: M. Mavronicolas, P. Tsigas (Eds.), 11th Internat. Workshop on Distributed Algorithms (WDAG), Lecture Notes in Computer Science, vol. 1320, Springer, Berlin, September 1997, pp. 37\u201351.","DOI":"10.1007\/BFb0030674"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB16","unstructured":"T. Eilam, D. Peleg, R.B. Tan, S. Zaks, Broadcast in linear messages in IRS representing all shortest paths, manuscript, 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB17","doi-asserted-by":"crossref","unstructured":"M. Flammini, Deadlock-free interval routing schemes, in: R. Reischuk, M. Morvan (Eds.), 14th Ann. Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 1200, Springer, Berlin, February 1997, pp. 351\u2013362.","DOI":"10.1007\/BFb0023472"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB18","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1142\/S0129626497000061","article-title":"On the hardness of devising interval routing schemes","volume":"7","author":"Flammini","year":"1997","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB19","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0304-3975(97)00070-4","article-title":"Multidimensional interval routing schemes","volume":"205","author":"Flammini","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB20","unstructured":"M. Flammini, G. Gambosi, U. Nanni, R.B. Tan, Characterization results of all shortest paths interval routing schemes, 5th Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), 1998, pp. 201\u2013213."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB21","doi-asserted-by":"crossref","unstructured":"M. Flammini, G. Gambosi, S. Salomone, Interval labeling schemes for chordal rings, in: P. Flocchini, B. Mans, N. Santoro (Eds.), 1st Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, May 1994, pp. 111\u2013124.","DOI":"10.1515\/9780773591158-008"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB22","doi-asserted-by":"crossref","unstructured":"M. Flammini, G. Gambosi, S. Salomone, Interval routing schemes, in: E.W. Mayr, C. Puech (Eds.), 12th Ann. Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 900, Springer, Berlin, March 1995, pp. 279\u2013290.","DOI":"10.1007\/3-540-59042-0_80"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB23","doi-asserted-by":"crossref","unstructured":"M. Flammini, E. Nardelli, On the path length in interval routing schemes, manuscript, 1996.","DOI":"10.1007\/BF01944351"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB24","doi-asserted-by":"crossref","unstructured":"M. Flammini, J. van Leeuwen, A. Marchetti-Spaccamela, The complexity of interval routing on random graphs, in: J. Wiederman, P. H\u00e1jek (Eds.), 20th Internat. Symp. on Mathematical Foundations of Computer Sciences (MFCS), Lecture Notes in Computer Science, vol. 969, Springer, Berlin, August 1995, pp. 37\u201349.","DOI":"10.1007\/3-540-60246-1_111"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB25","doi-asserted-by":"crossref","unstructured":"P. Flocchini, F.L. Luccio, Distance routing on series parallel networks, in: 16th IEEE Internat. Conf. on Distributed Computing Systems, March 1996, pp. 352\u2013359.","DOI":"10.1109\/ICDCS.1996.507969"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB26","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0020-0190(97)00091-4","article-title":"On the impact of sense of direction on communication complexity","volume":"63","author":"Flocchini","year":"1997","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB27","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<165::AID-NET1>3.0.CO;2-I","article-title":"Sense of direction: definitions, properties and classes","volume":"32","author":"Flocchini","year":"1998","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB28","doi-asserted-by":"crossref","unstructured":"P. Flocchini, B. Mans, N. Santoro, Sense of direction in distributed computing, in: S. Kutten (Ed.), 12th Internat. Symp. on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 1499, Springer, Berlin, September 1998, pp. 1\u201315.","DOI":"10.1007\/BFb0056468"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB29","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s004460050025","article-title":"Universal routing schemes","volume":"10","author":"Fraigniaud","year":"1997","journal-title":"J. Distributed Comput."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB30","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/PL00009211","article-title":"Interval routing schemes","volume":"21","author":"Fraigniaud","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB31","unstructured":"P. Fraigniaud, C. Gavoille, D. Krizanc, Communication during the visit of Danny Krizanc at LIP, Ecole Normale Sup\u00e9rieure de Lyon, February 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB32","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","article-title":"Designing networks with compact routing tables","volume":"3","author":"Frederickson","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB33","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/0219011","article-title":"Space-efficient message routing in c-decomposable networks","volume":"19","author":"Frederickson","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB34","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","article-title":"A distributed algorithm for minimal spanning tree","volume":"30","author":"Gallager","year":"1983","journal-title":"ACM Trans. Programming Languages Systems"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB35","doi-asserted-by":"crossref","unstructured":"G. Gambosi, P. Vocca, Topological routing schemes, in: \u00d6. Babao\u011flu, K. Marzullo (Eds.), 10th Internat. Workshop on Distributed Algorithms (WDAG), Lecture Notes in Computer Science, vol. 1151, Springer, Berlin, October 1996, pp. 206\u2013219.","DOI":"10.1007\/3-540-61769-8_14"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB36","unstructured":"C. Gavoille, Lower bounds for interval routing on bounded degree networks, Research Report, RR-1144-96, LaBRI, University of Bordeaux, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France, October 1996."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB37","doi-asserted-by":"crossref","unstructured":"C. Gavoille, On the dilation of interval routing, in: I. Pr\u0131\u0301vara, P. Ru\u017ei\u010dka (Eds.), 22nd Internat. Symp. on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 1300, Springer, Berlin, August 1997, pp. 259\u2013268.","DOI":"10.1007\/BFb0029969"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1997.0915","article-title":"Worst case bounds For shortest path interval routing","volume":"27","author":"Gavoille","year":"1988","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB39","unstructured":"C. Gavoille, B. Mans, Private communication, August 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB40","unstructured":"C. Gavoille, D. Peleg, The compactness of interval routing, Research Report RR-1176-97, LaBRI, University of Bordeaux, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France, September 1997, SIAM J. Discrete Mathematics, to appear."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB41","doi-asserted-by":"crossref","unstructured":"C. Gavoille, D. Peleg, The compactness of interval routing for almost all graphs, in: S. Kutten (Ed.), 12th Internat. Symp. on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 1499, Springer, Berlin, September 1998, pp. 161\u2013174.","DOI":"10.1007\/BFb0056481"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB42","unstructured":"C. Gavoille, S. P\u00e9renn\u00e8s, Lower bounds for interval routing on 3-regular networks, in: N. Santoro, P. Spirakis (Eds.), 3rd Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, June 1996, pp. 88\u2013103."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB43","series-title":"15th Ann. ACM Symp. on Principles of Distributed Computing (PODC)","first-page":"125","article-title":"Memory requirement for routing in distributed networks","author":"Gavoille","year":"1996"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB44","doi-asserted-by":"crossref","unstructured":"M.C.Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, Harcourt Brace, Jovanovich, Academic Press ed., 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB45","series-title":"Combinatorial Theory","author":"Hall","year":"1986"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB46","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0166-218X(89)90022-X","article-title":"On forwarding indices of networks","volume":"23","author":"Heydemann","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB47","doi-asserted-by":"crossref","unstructured":"H. Hofest\u00e4dt, A. Klein, E. Reyzl, Performance benefits from locally adaptative interval routing in dynamically switched interconnection networks, in: A. Bode (Ed.), Distributed Memory Computing: 2nd Eur. Conf. EDMCC2, Lecture Notes in Computer Science, vol. 487, Munich, April 1991, Springer, Berlin, pp. 193\u2013202.","DOI":"10.1007\/BFb0032936"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB48","unstructured":"M. Juganaru, Routage avec table de routage compacte, stage de DEA, ENSIMAG, Grenoble, June 1993."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB49","doi-asserted-by":"crossref","unstructured":"T. Kloks, Treewidth: Computations and Approximations, Lectures Notes in Computer Science, vol. 842, Springer, Berlin, June 1994.","DOI":"10.1007\/BFb0045375"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB50","doi-asserted-by":"crossref","unstructured":"R. Kr\u00e1\u013eovi\u010d, B. Rovan, P. Ru\u017ei\u010dka, D. \u0160tefankovi\u010d, Efficient deadlock-free multi-dimensional interval routing in interconnection networks, in: S. Kutten (Ed.), 12th Internat. Symp. on Distributed Computing (DISC), Lectures Notes in Computer Science, vol. 1499, Springer, Berlin, September 1998, pp. 273\u2013287.","DOI":"10.1007\/BFb0056489"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB51","doi-asserted-by":"crossref","unstructured":"R. Kr\u00e1\u013eovi\u010d, P. Ru\u017ei\u010dka, D. \u0160tefankovi\u010d, The complexity of shortest path and dilation bounded interval routing, in: C. Lengaur, M. Griebl, S. Gorlatch (Eds.), 3rd Internat. Euro-Par Conf., Lectures Notes in Computer Science, vol. 1300, Springer, Berlin, August 1997, pp. 258\u2013265.","DOI":"10.1007\/BFb0002742"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB52","doi-asserted-by":"crossref","unstructured":"R. Kr\u00e1\u013eovi\u010d, P. Ruz\u0306ic\u0306ka, D. \u0160tefankovi\u010d, The complexity of shortest path and dilation bounded interval routing, (full version of [51]), Theoret. Comput. Sci. 1997, to appear.","DOI":"10.1007\/BFb0002742"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB53","doi-asserted-by":"crossref","unstructured":"E. Kranakis, D. Krizanc, Lower bounds for compact routing, in: C. Puech, R. Reischuk (Eds.), 13th Ann. Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 1046, Springer, Berlin, February 1996.","DOI":"10.1007\/3-540-60922-9_43"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB54","doi-asserted-by":"crossref","unstructured":"E. Kranakis, D. Krizanc, S.S. Ravi, On multi-label linear interval routing schemes, in: 19th Internat. Workshop on Graph \u2013 Theoretic Concepts in Computer Science \u2013 Distributed Algorithms (WG), Lecture Notes in Computer Science, vol. 790, Springer, Berlin, June 1993, pp. 338\u2013349.","DOI":"10.1007\/3-540-57899-4_64"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB55","unstructured":"D. Krizanc, F.L. Luccio, Boolean routing on chordal rings, in: L.M. Kirousis, E. Kranakis (Eds.), 2nd Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, June 1995, pp. 89\u2013100."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB56","series-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"Li","year":"1993"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB57","doi-asserted-by":"crossref","unstructured":"P. Loh, J. Wenge, Adaptive, fault-tolerant, deadlock-free and livelock-free interval routing in mesh networks, in: 2nd IEEE Internat. Conf. on Algorithms & Architectures for Parallel Processing (ICAPP), June 1996, pp. 348\u2013355.","DOI":"10.1109\/ICAPP.1996.562895"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB58","doi-asserted-by":"crossref","unstructured":"B. Mans, On the interval routing of chordal rings of degree 4, in: Zomaya, Hsu, Ibarra, Horiguchi, Nassimi and Palis, International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), June 1999, pp. 16\u201321.","DOI":"10.1109\/ISPAN.1999.778911"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB59","unstructured":"D. May, P. Thompson, Transputers and Routers: Components for concurrent machines, INMOS Ltd., 1990."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB60","unstructured":"L. Narayanan, N. Nishimura, Interval routing on k-trees, in: N. Santoro, P. Spirakis (Eds.), 3rd Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, June 1996, pp. 104\u2013118."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB61","unstructured":"L. Narayanan, J. Opatrny, Compact routing on chordal rings of degree four, in: D. Krizanc, P. Widmayer (Eds.), 4th Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton Scientific, July 1997, pp. 125\u2013137."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB62","unstructured":"L. Narayanan, S. Shende, Characterizations of networks supporting shortest-path interval labeling schemes, in: N. Santoro, P. Spirakis (Eds.), 3rd Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, June 1996, pp. 73\u201387."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB63","doi-asserted-by":"crossref","unstructured":"D. Peleg, E. Upfal, A trade-off between space and efficiency for routing tables, in: 20th Ann. ACM Symp. on Theory of Computing (STOC), Chicago, IL, May 1988, pp. 43\u201352.","DOI":"10.1145\/62212.62217"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB64","first-page":"492","article-title":"On efficiency of interval routing algorithms","volume":"vol. 324","author":"Ru\u017ei\u010dka","year":"1988"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB65","unstructured":"P. Ru\u017ei\u010dka, D. \u0160tefankovi\u010d, On the complexity of multi-dimensional interval routing schemes, Theoret. Comput. Sci. 1997, Submitted for publication."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB66","series-title":"IFIP Transactions","first-page":"297","article-title":"Routing with compact tables","author":"Sakho","year":"1994"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB67","unstructured":"N. Santoro, R. Khatib, Routing without routing tables, Technical Report SCS-TR-6 School of Computer Science, Carleton University, Ottawa, 1982."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB68","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","article-title":"Labelling and implicit routing in networks","volume":"28","author":"Santoro","year":"1985","journal-title":"Comp. J."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB69","unstructured":"H. Schomberg, Chord and shuffle augmented mesh topologies for messages-passing multicomputers, manuscript, 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB70","unstructured":"Siena Research School, Communication at the Siena Research School \u201997 on \u201cCompact Routing and Sense of Direction\u201d, June 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB71","series-title":"Introduction to Distributed Algorithms","author":"Tel","year":"1994"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB72","unstructured":"S.S.H. Tse, F.C.M. Lau, Lower bounds for multi-label interval routing, in: L.M. Kirousis, E. Kranakis (Eds.), 2nd Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, June 1995, pp. 123\u2013134."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB73","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1002\/(SICI)1097-0037(199701)29:1<49::AID-NET5>3.0.CO;2-C","article-title":"A lower bound for interval routing in general networks","volume":"29","author":"Tse","year":"1997","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB74","unstructured":"S.S.H. Tse, F.C.M. Lau, An optimal lower bound for interval routing in general networks, in: D. Krizanc, P. Widmayer (Eds.), 4th Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton Scientific, July 1997, pp. 112\u2013124."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB75","unstructured":"S.S.H. Tse, F.C.M. Lau, Some lower-bound results on interval routing in planar graphs, Technical Report TR-97-05, Department of Computer Science, The University of Hong Kong, April 1997."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB76","unstructured":"J. van Leeuwen, R.B. Tan, Routing with compact routing tables, Technical Report RUU-CS-83-16, Department of Computer Science, University of Utrecht, Utrecht, November 1983."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB77","series-title":"The Book","first-page":"259","article-title":"Computer networks with compact routing tables","author":"van Leeuwen","year":"1986"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB78","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1093\/comjnl\/30.4.298","article-title":"Interval routing","volume":"30","author":"van Leeuwen","year":"1987","journal-title":"Comput. J."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB79","doi-asserted-by":"crossref","unstructured":"J. van Leeuwen, R.B. Tan, Compact routing methods: a survey, in: P. Flocchini, B. Mans, N. Santoro (Eds.), 1st Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, May 1994, pp. 99\u2013110.","DOI":"10.1515\/9780773591158-007"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB80","doi-asserted-by":"crossref","unstructured":"J. Vounckx, G. Deconinck, R. Lauwereins, J.A. Peperstraete, Fault-tolerant compact routing based on reduced structural information in wormhole-switching based networks, in: P. Flocchini, B. Mans, N. Santoro (Eds.), 1st Internat. Coll. on Structural Information & Communication Complexity (SIROCCO), Carleton University Press, May 1994, pp. 125\u2013147.","DOI":"10.1515\/9780773591158-009"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB81","unstructured":"A. Zemmari, Routage compact et adaptatif, stage de DEA, Universit\u00e9 de Bordeaux, 351 cours de la Lib\u00e9ration, 33405 Talence cedex, France, June 1997, \u201chttp:\/\/www.labri.u-bordeaux.fr\/\u00a0\u0303gavoille\/article\/Zemmari97.ps.gz\u201d, An English version is in preparation."},{"key":"10.1016\/S0304-3975(99)00283-2_BIB82","doi-asserted-by":"crossref","unstructured":"B. Zerrouk, J. Blin, A. Greiner, Encapsuling networks and routing, in 8th Internat. Parallel Process. Symp. (IPPS), 1994, pp. 546\u2013553.","DOI":"10.1109\/IPPS.1994.288250"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB83","doi-asserted-by":"crossref","unstructured":"B. Zerrouk, V. Reibaldi, F. Potter, A. Greiner, D. Anne, RCube: a gigabit serial links low latency adaptive router, in the Records of the IEEE Hot Interconnects IV, Palo Alto CA, U.S.A, August 1996.","DOI":"10.1109\/ICECS.1996.582821"},{"key":"10.1016\/S0304-3975(99)00283-2_BIB84","unstructured":"B. Zerrouk, S. Tricot, B. Rottembourg, L. Patnaik, Proper linear interval routing schemes, Technical Report N 94-29, IBP-MASI, October 1994."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002832?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599002832?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,12,31]],"date-time":"2023-12-31T10:56:09Z","timestamp":1704020169000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599002832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":84,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0304397599002832"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00283-2","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}