{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T12:21:39Z","timestamp":1790943699436,"version":"4.1.0"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>This paper is concerned with compact routing schemes for arbitrary undirected networks in the name\u2010independent model first introduced by Awerbuch, Bar\u2010Noy, Linial, and Peleg. A compact routing scheme that uses local routing tables of size $\\~{O}(n^{1\/2})$, $O(\\log^2 n)$\u2010sized packet headers, and stretch bounded by 5 is obtained, where n is the number of nodes in the network. (We use the notation $\\~{O}\\left(f(n)\\right)$ to represent $O(f(n)\\log^c{n})$, where c is an arbitrary nonnegative real number, independent of n.) Alternative schemes reduce the packet header size to $O(\\log n)$ at the cost of either increasing the stretch to 7 or increasing the table size to $\\~{O}(n^{2\/3})$. For smaller table\u2010size requirements, the ideas in these schemes are generalized to a scheme that uses $O(\\log^2 n)$\u2010sized headers and ${O}(k^2n^{2\/k})$\u2010sized tables, and achieves a stretch of $\\min\\{1 + (k-1)(2^{k\/2}-2), 16k^2-8k\\}$, improving the best previously known name\u2010independent scheme due to Awerbuch and Peleg.<\/jats:p>","DOI":"10.1137\/04062053","type":"journal-article","created":{"date-parts":[[2006,10,4]],"date-time":"2006-10-04T18:12:11Z","timestamp":1159985531000},"page":"705-726","source":"Crossref","is-referenced-by-count":6,"title":["Compact Routing with Name Independence"],"prefix":"10.1137","volume":"20","author":[{"given":"Marta","family":"Arias","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lenore J.","family":"Cowen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kofi A.","family":"Laing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Orjeta","family":"Taka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,9,29]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Abraham, C. Gavoille, and D. Malkhi,\n                      Routing with improved communication\u2010space trade\u2010off\n                      , in Proceedings of the 18th International Symposium on Distributed Computing (DISC), R. Guerraoui, ed., Lecture Notes in Comput. Sci. 3274, Springer, Berlin, 2004, pp. 305\u2013319.","DOI":"10.1007\/978-3-540-30186-8_22"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Arias, L. Cowen, K. Laing, R. Rajaraman, and O. Taka,\n                      Compact routing with name independence\n                      , in Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM, New York, 2003, pp. 184\u2013192.","DOI":"10.1145\/777412.777442"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and D. Peleg,\n                      Sparse partitions\n                      , in Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 1990, pp. 503\u2013513.","DOI":"10.1109\/FSCS.1990.89571"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Bar\u2010Noy, N. Linial, and D. Peleg,\n                      Compact distributed data structures for adaptive network routing\n                      , in Proceedings of the 21st ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 479\u2013489.","DOI":"10.1145\/73007.73053"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90017-9"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup,\n                      Compact name\u2010independent routing with minimum stretch\n                      , in Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), ACM, New York, 2004, pp. 20\u201324.","DOI":"10.1145\/1007912.1007916"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"D. Dor, S. Halperin, and U. Zwick,\n                      All pairs almost shortest paths\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 452\u2013461.","DOI":"10.1109\/SFCS.1996.548504"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"T. Eilam, C. Gavoille, and D. Peleg,\n                      Compact routing schemes with low stretch factor\n                      , in Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1998, pp. 11\u201320.","DOI":"10.1145\/277697.277702"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud and C. Gavoille,\n                      Routing in trees\n                      , in 28th International Colloquium on Automata, Languages and Programming (ICALP), F. Orejas, P. G. Spirakis, and J. van Leeuwen, eds., Lecture Notes in Comput. Sci. 2076, Springer, Berlin, 2001, pp. 757\u2013772.","DOI":"10.1007\/3-540-48224-5_62"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1705"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"K. Hildrum, J. Kubiatowicz, S. Rao, and B. Zhao,\n                      Distributed object location in a dynamic network\n                      , in Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 2002, pp. 41\u201352.","DOI":"10.1145\/564870.564877"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. Krioukov, K. Fall, and X. Yang,\n                      Compact routing on Internet\u2010like graphs\n                      , in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom 2004), 2004, pp. 209\u2013219.","DOI":"10.1109\/INFCOM.2004.1354495"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/356989.357007"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"T. Leighton,\n                      Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes\n                      , Morgan Kaufmann, San Mateo, CA, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1020"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000118"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick,\n                      Compact routing schemes\n                      , in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 2001, pp. 1\u201310.","DOI":"10.1145\/378580.378581"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick,\n                      Approximate distance oracles\n                      , in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 183\u2013192.","DOI":"10.1145\/380752.380798"},{"key":"R23","unstructured":"M. van Steen, F. J. Hauck, and A. S. Tanenbaum,\n                      A model for worldwide tracking of distributed objects\n                      , in Proceedings of the 1996 Conference on Telecommunications Information Networking Architecture (TINA 96), 1996, pp. 203\u2013212."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/04062053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:16Z","timestamp":1787322916000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/04062053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/04062053"],"URL":"https:\/\/doi.org\/10.1137\/04062053","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}