{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:46Z","timestamp":1725664486596},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_43","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:31Z","timestamp":1330290271000},"page":"529-540","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds for compact routing"],"prefix":"10.1007","author":[{"given":"Evangelos","family":"Kranakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"unstructured":"V. Braune, \u201cTheoretische und experimentelle Analyse von Intervall Routing Algorithmen\u201d, Master Thesis, Department of Mathematics and Computer Science, University of Padenborn, 1993.","key":"43_CR1"},{"doi-asserted-by":"crossref","unstructured":"H. Buhrman, J.-H. Hoepman, and P. Vit\u00e1nyi, \u201cOptimal Routing\u201d, Unpublished draft, July 1995.","key":"43_CR2","DOI":"10.1145\/248052.248076"},{"key":"43_CR3","first-page":"219","volume":"725","author":"M. Flammini","year":"1993","unstructured":"M. Flammini, G. Gambosi and S. Salomone, \u201cBoolean Routing\u201d, in proceedings of WDAG'93, Springer Verlag LNCS Vol. 725, pp. 219\u2013233, 1993.","journal-title":"Springer Verlag LNCS"},{"doi-asserted-by":"crossref","unstructured":"M. Flammini, J. van Leeuwen, and A. Marchetti-Spaccamela, \u201cThe Complexity of Interval Routing on Random Graphs\u201d, In proceedings of MFCS, Springer Verlag LNCS, 1995, to appear.","key":"43_CR4","DOI":"10.1007\/3-540-60246-1_111"},{"doi-asserted-by":"crossref","unstructured":"P. Fraigniaud and C. Gavoille, \u201cMemory Requirement for Universal Routing Schmes\u201d, In proceedings of ACM conference on Principles of Distributed Computing, 1995, to appear.","key":"43_CR5","DOI":"10.1145\/224964.224989"},{"doi-asserted-by":"crossref","unstructured":"G. N. Fredrickson and R. Janardan, \u201cDesigning Networks with Compact Routing Tables\u201d, Algorithmica, pp. 171\u2013190, 1988.","key":"43_CR6","DOI":"10.1007\/BF01762113"},{"issue":"4","key":"43_CR7","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1137\/0218058","volume":"18","author":"G. N. Fredrickson","year":"1989","unstructured":"G. N. Fredrickson and R. Janardan, \u201cEfficient Message Routing in Planar Networks\u201d, SIAM Journal on Comp. 18(4) 843\u2013857, 1989.","journal-title":"SIAM Journal on Comp."},{"issue":"1","key":"43_CR8","first-page":"184","volume":"19","author":"G. N. Fredrickson","year":"1990","unstructured":"G. N. Fredrickson and R. Janardan, \u201cSpace-Efficient Message Routing in c-Decomposable Networks\u201d, SIAM Journal on Comp. 19(1) 184\u2013181, 1990.","journal-title":"SIAM Journal on Comp."},{"key":"43_CR9","volume-title":"On the Compactness of Bounded Degree Graphs for Shortest Parh Interval Routing","author":"C. Gavoille","year":"1995","unstructured":"C. Gavoille and E. Gu\u00e9vremont, \u201cOn the Compactness of Bounded Degree Graphs for Shortest Parh Interval Routing\u201d, in proceedings of 2nd International Conference on Structure Information and Communication Complexity, June 12\u201314, Olympia, Greece, 1995, Carleton University Press, to appear."},{"unstructured":"C. Gavoille and E. Gu\u00e9vremont, \u201cWorst Case Bounds for Shortest Path Interval Routing\u201d, ENS Lyon, Technical Report, Jan. 20, 1995.","key":"43_CR10"},{"unstructured":"E. Kranakis, D. Krizanc and S. S. Ravi, \u201cOn Multiple Linear Interval Routing Schemes\u201d, in proceedings of WG'93 (Workshop on Graph Theoretic Concepts in Computer Science), Vol. 790, Springer Verlag LNCS.","key":"43_CR11"},{"doi-asserted-by":"crossref","unstructured":"M. Li and P. Vitanyi, \u201cIntroduction to Kolmogorov Complexity and its Applications\u201d Springer Verlag, 1993.","key":"43_CR12","DOI":"10.1007\/978-1-4757-3860-5"},{"doi-asserted-by":"crossref","unstructured":"D. Peleg and E. Upfal \u201cA Tradeoff between Space and Efficiency for Routing Tables\u201d, in ACM STOC 1988, pages 43\u201352 (also in Journal of ACM, Vol. 36, pages 510\u2013530, 1989).","key":"43_CR13","DOI":"10.1145\/65950.65953"},{"issue":"no.1","key":"43_CR14","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N. Santoro","year":"1985","unstructured":"N. Santoro and R. Khatib, \u201cLabelling and Implicit Routing in Networks\u201d, The Computer Journal, vol. 28, no. 1, 1985, pp. 5\u20138.","journal-title":"The Computer Journal"},{"key":"43_CR15","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":"J. van Leeuwen and R. B. Tan, \u201cComputer Networks with Compact Routing Tables\u201d, in The Book of L, Edited by G. Rozenberg and A. Salomaa, Springer-verlag, Berlin 1986, pp 259\u2013273."},{"issue":"no.4","key":"43_CR16","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1093\/comjnl\/30.4.298","volume":"30","author":"J. Leeuwen van","year":"1987","unstructured":"J. van Leeuwen and R. B. Tan, \u201cInterval Routing\u201d, The Computer Journal, vol. 30, no. 4, 1987, pp. 298\u2013307.","journal-title":"The Computer Journal"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:19:40Z","timestamp":1578536380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_43"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}