{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:48Z","timestamp":1750694688227},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_4","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"65-75","source":"Crossref","is-referenced-by-count":18,"title":["A Space Lower Bound for Routing in Trees"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch and David Peleg. Sparse partitions. In 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 503\u2013513. IEEE Computer Society Press, October 1990.","DOI":"10.1109\/FSCS.1990.89571"},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B. Awerbuch","year":"1992","unstructured":"Baruch Awerbuch and David Peleg. Routing with polynomial communicationspace trade-off. SIAM Journal on Discrete Mathematics, 5(2):151\u2013162, May 1992.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L. J. Cowen","year":"2001","unstructured":"Lenore J. Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38:170\u2013183, 2001.","journal-title":"Journal of Algorithms"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. In 17 th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 11\u201320. ACM PRESS, August 1998.","DOI":"10.1145\/277697.277702"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Paul Erd\u00f6s. Extremal problems in graph theory. In Publ. House Cszechoslovak Acad. Sci., Prague, pages 29\u201336, 1964.","DOI":"10.4064\/cm-13-2-251-254"},{"key":"4_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"28 th International Colloquium on Automata, Languages and Programming (ICALP)","author":"P. Fraigniaud","year":"2001","unstructured":"Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In 28 th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757\u2013772. Springer, July 2001."},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(99)00283-2","volume":"245","author":"C. Gavoille","year":"2000","unstructured":"Cyril Gavoille. A survey on interval routing. Theoretical Computer Science, 245(2):217\u2013253, 2000.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/568438.568451","volume":"32","author":"C. Gavoille","year":"2001","unstructured":"Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News \u2014 Distributed Computing Column, 32(1):36\u201352, March 2001.","journal-title":"ACM SIGACT News \u2014 Distributed Computing Column"},{"key":"4_CR9","unstructured":"Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Research Report RR-1261-01, LaBRI, University of Bordeaux, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France, August 2001. To appear in Journal of Distributed Computing."},{"key":"4_CR10","unstructured":"Cyril Gavoille, David Peleg, St\u00e9phane P\u00e9rennes, and Ran Raz. Distance labeling in graphs. In 12 th Symposium on Discrete Algorithms (SODA), pages 210\u2013219. ACM-SIAM, January 2001."},{"key":"4_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/3-540-44612-5_53","volume-title":"Informative labeling schemes for graphs","author":"D. Peleg","year":"2000","unstructured":"David Peleg. Informative labeling schemes for graphs. In 25th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 1893 of Lecture Notes in Computer Science, pages 579\u2013588. Springer, August 2000."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33:167\u2013176, 2000.","journal-title":"Journal of Graph Theory"},{"issue":"3","key":"4_CR13","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510\u2013530, July 1989.","journal-title":"Journal of the ACM"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup and Uri Zwick. Approximate distance oracles. In 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 183\u2013192, Hersonissos, Crete, Greece, July 2001.","DOI":"10.1145\/380752.380798"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup and Uri Zwick. Compact routing schemes. In 13 th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1\u201310, Hersonissos, Crete, Greece, July 2001. ACM PRESS.","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:00:01Z","timestamp":1556755201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}