{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:47:39Z","timestamp":1777459659307,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540233060","type":"print"},{"value":"9783540301868","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30186-8_22","type":"book-chapter","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T15:48:23Z","timestamp":1285170503000},"page":"305-319","source":"Crossref","is-referenced-by-count":21,"title":["Routing with Improved Communication-Space Trade-Off"],"prefix":"10.1007","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dahlia","family":"Malkhi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: Routing with improved communication- space trade-off, Tech. Report RR-1330-04, LaBRI, University of Bordeaux 1, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France (July 2004)"},{"key":"22_CR2","first-page":"20","volume-title":"16th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA)","author":"I. Abraham","year":"2004","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. In: 16th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), pp. 20\u201324. ACM Press, New York (2004)"},{"key":"22_CR3","first-page":"184","volume-title":"15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"M. Arias","year":"2003","unstructured":"Arias, M., Cowen, L., Laing, K., Rajaraman, R., Taka, O.: Compact routing with name independence. In: 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2003, pp. 184\u2013192. ACM Press, New York (2003)"},{"key":"22_CR4","first-page":"479","volume-title":"21st Annual ACM Symposium on Theory of Computing (STOC)","author":"B. Awerbuch","year":"1989","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Compact distributed data structures for adaptive routing. In: 21st Annual ACM Symposium on Theory of Computing (STOC), May 1989, pp. 479\u2013489. ACM Press, New York (1989)"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0196-6774(90)90017-9","volume":"11","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Noy, A.B., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. Journal of Algorithms\u00a011, 307\u2013341 (1990)","journal-title":"Journal of Algorithms"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1990, pp. 503\u2013513 (1990)","DOI":"10.1109\/FSCS.1990.89571"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B. Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM J. Discret. Math.\u00a05, 151\u2013162 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal hash functions. Journal of Computer and System Sciences\u00a018, 143\u2013154 (1979)","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L.J. Cowen","year":"2001","unstructured":"Cowen, L.J.: Compact routing with minimum stretch. Journal of Algorithms\u00a038, 170\u2013183 (2001)","journal-title":"Journal of Algorithms"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/568438.568451","volume":"32","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C.: Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column\u00a032, 36\u201352 (2001)","journal-title":"ACM SIGACT News - Distributed Computing Column"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Gengler, M.: Space-efficiency of routing schemes of stretch factor three. J. of Parallel and Distributed Computing\u00a061, 679\u2013687 (2001)","journal-title":"J. of Parallel and Distributed Computing"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. J. of Distributed Computing\u00a016, 111\u2013120 (2003); PODC 20-Year Special Issue","journal-title":"J. of Distributed Computing"},{"key":"#cr-split#-22_CR14.1","unstructured":"Laing, K.: Name-independent compact routing in trees, Tech. Report 2003-02, Tufts Univ. Dep. of Comp. Science (November 2003);"},{"key":"#cr-split#-22_CR14.2","unstructured":"Also in PODC 2004 as brief announcements (2004)"},{"key":"22_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Camb. Univ. Press, Cambridge (1995)"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM\u00a036, 510\u2013530 (1989)","journal-title":"Journal of the ACM"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N. Santoro","year":"1985","unstructured":"Santoro, N., Khatib, R.: Labelling and implicit routing in networks. The Computer Journal\u00a028, 5\u20138 (1985)","journal-title":"The Computer Journal"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"},{"key":"22_CR20","first-page":"1","volume-title":"13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2001, pp. 1\u201310. ACM Press, New York (2001)"},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"22_CR22","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-642-95486-3_22","volume-title":"The Book of L","author":"J. Leeuwen van","year":"1986","unstructured":"van Leeuwen, J., Tan, R.B.: Computer networks with compact routing tables. In: The Book of L, pp. 259\u2013273. Springer, Heidelberg (1986)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30186-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:53:31Z","timestamp":1619999611000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30186-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540233060","9783540301868"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30186-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}