{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T00:33:42Z","timestamp":1769733222248,"version":"3.49.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a\n            <jats:italic>\u00d5<\/jats:italic>\n            (\u221an,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires \u03a9(\u221a\n            <jats:italic>n<\/jats:italic>\n            ,)space per node.\n          <\/jats:p>","DOI":"10.1145\/1367064.1367077","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Compact name-independent routing with minimum stretch"],"prefix":"10.1145","volume":"4","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[{"name":"University of Bordeaux, Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dahlia","family":"Malkhi","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel &amp; Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research, Florham Park, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777442"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73053"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90017-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Aalgorithms. ACM","author":"Cowen L. J.","year":"1999"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00002-6"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 28th International Colloqium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"2076","author":"Fraigniaud P."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science","volume":"2285","author":"Fraigniaud P."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/568438.568451"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1705"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0073-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.]]   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.]]","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367077","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:54Z","timestamp":1750255074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367077"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367077","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}