{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T06:06:38Z","timestamp":1649052398566},"reference-count":22,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"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":3942,"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":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00180-3","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T20:25:18Z","timestamp":1034022318000},"page":"85-104","source":"Crossref","is-referenced-by-count":6,"title":["The complexity of the characterization of networks supporting shortest-path interval routing"],"prefix":"10.1016","volume":"289","author":[{"given":"T.","family":"Eilam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Moran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Zaks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00180-3_BIB1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, D. Peleg, Sparse partitions. Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 514\u2013522.","DOI":"10.1109\/FSCS.1990.89571"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB2","unstructured":"E.M. Bakker, R.B. Tan, J. van Leeuwen, Manuscript, 1994."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB3","first-page":"45","article-title":"Linear interval routing","volume":"2","author":"Bakker","year":"1991","journal-title":"Algorithms Rev."},{"issue":"1","key":"10.1016\/S0304-3975(01)00180-3_BIB4","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. and Comput."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB5","doi-asserted-by":"crossref","unstructured":"T. Eilam, C. Gavoille, D. Peleg, Compact routing schemes with low stretch factor. Proc. 17th ACM Symp. on Principles of Distributed Computing (PODC), 1998 (Also as Technical Report RR-1195-98, Laboratoire Bordelais de Recherche en Informatique, Universite Bordeaux I, Talence Cedex, France, January).","DOI":"10.1145\/277697.277702"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB6","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, C. Gavoille, Optimal interval routing, in: B. Buchberger, J. Volkert (Eds.), Parallel Processing: CONPAR 94-VAPP VI Third Joint Int. Conf. Vector and Parallel Processing, Linz, Austria, September 1994.","DOI":"10.1007\/3-540-58430-7_68"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB7","doi-asserted-by":"crossref","unstructured":"M. Flammini, G. Gambosi, S. Salomone, Interval routing schemes, Proc. Symp. on Theoretical Aspects of Computer Science (STACS), 1995, pp. 279\u2013290.","DOI":"10.1007\/3-540-59042-0_80"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB8","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"},{"issue":"1","key":"10.1016\/S0304-3975(01)00180-3_BIB9","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(01)00180-3_BIB10","unstructured":"C. Gavoille, On the dilation of interval routing, Comput. J. 43(1) (2000) 1\u20137 (Also appeared in 22nd Int. Symp. on Mathematical Foundations of Computer Science (MFCS), Springer, Lecture Notes in Computer Science, Vol. 1300, Springer, Berlin, 1997, pp. 259\u2013268."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB11","doi-asserted-by":"crossref","unstructured":"C. Gavoille, A survey on interval routing, Theoret. Comput. Sci. 245(2) (2000) 217\u2013253 (Also as: RR-1182-97, University of Bordeaux, Talence Cedex, France, October, 1997).","DOI":"10.1016\/S0304-3975(99)00283-2"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB12","doi-asserted-by":"crossref","unstructured":"C. Gavoille, E. Gu\u00e9vremont, Worst case bounds for shortest path interval routing. J. Algorithms, 27 (1998) 1\u201325 (Also as: Research Report 95-02, \u00c9cole Normale Sup\u00e9rieure de Lyon, Lyon Cedex, France, January, 1995).","DOI":"10.1006\/jagm.1997.0915"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB13","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB14","unstructured":"Inmos, The T9000 Transputer Products Overview Manual, SGS-Thomson, Microelectronics, 1991."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB15","doi-asserted-by":"crossref","unstructured":"E. Kranakis, D. Krizanc, S. Ravi, On multi-label linear interval routing schemes, Workshop on Graph-Theoretic Concepts in Computer Science (WG), 1993, pp. 338\u2013349.","DOI":"10.1007\/3-540-57899-4_64"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB16","unstructured":"L. Narayanan, S. Shende, Characterization of networks supporting shortest path interval routing schemes, Proc. 3rd Internat. Colloq. on Structural Information and Communication Complexity, 1996 (Also as: Technical Report, Concordia University, 1995)."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB17","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","article-title":"A trade-off between size and efficiency for routing tables","volume":"36","author":"Peleg","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB18","series-title":"Surveys in Combinatorics","first-page":"153","article-title":"Graphs minors\u2014a survey","author":"Robertson","year":"1985"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB19","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","article-title":"Labeling and implicit routing in networks","volume":"28","author":"Santoro","year":"1985","journal-title":"Comput. J."},{"key":"10.1016\/S0304-3975(01)00180-3_BIB20","series-title":"The book of L","article-title":"Routing with compact routing tables","author":"van Leeuwen","year":"1986"},{"key":"10.1016\/S0304-3975(01)00180-3_BIB21","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(01)00180-3_BIB22","unstructured":"B. Zerrouk, S. Tricot, B. Rottembourg, L.M. Patnaik, Proper linear interval routing schemes. Technical Report, Institut Blaise Pascal, Univ. Pierre et Marie Curie, Paris, 1993."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001803?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001803?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T17:53:54Z","timestamp":1583776434000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501001803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501001803"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00180-3","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}