{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T17:07:33Z","timestamp":1742404053859},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_35","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"376-386","source":"Crossref","is-referenced-by-count":15,"title":["A Doubling Dimension Threshold \u0398(loglogn) for Augmented Graph Navigability"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuelle","family":"Lebhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th International Conference on Distributed Computing Systems (ICDCS) (to appear, 2006)","DOI":"10.1109\/ICDCS.2006.72"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D.: Name independent routing for growth bounded networks. In: 17th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), pp. 49\u201355 (2005)","DOI":"10.1145\/1073970.1073978"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: 21st ACM Symp. on Principles of Distributed Computing (PODC), pp. 223\u2013232 (2002)","DOI":"10.1145\/571825.571862"},{"issue":"4","key":"35_CR4","first-page":"429","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipshitzien dans R n . Bull. Soc. Math.\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math."},{"key":"35_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-45414-4_19","volume-title":"Distributed Computing","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long range contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 270\u2013284. Springer, Heidelberg (2001)"},{"key":"35_CR6","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 762\u2013771 (2005)"},{"key":"35_CR7","volume-title":"Nearest-neighbor searching and metric space dimensions (Survey)","author":"K.L. Clarkson","year":"2006","unstructured":"Clarkson, K.L.: Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. In: Darrell, T., Indyk, P., Shakhnarovich, G., Viola, P. (eds.) Nearest-neighbor searching and metric space dimensions (Survey). MIT Press, Cambridge (2006)"},{"issue":"1","key":"35_CR8","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2005.12.008","volume":"355","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small world? Theoretical Computer Science\u00a0355(1), 96\u2013103 (2006); Special issue on Complex Networks","journal-title":"Theoretical Computer Science"},{"key":"35_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/11561927_30","volume-title":"Distributed Computing","author":"M. Flammini","year":"2005","unstructured":"Flammini, M., Moscardelli, L., Navarra, A., Perennes, S.: Asymptotically optimal solutions for small world graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 414\u2013428. Springer, Heidelberg (2005)"},{"key":"35_CR10","unstructured":"Fomenkov, M., Claffy, K., Huffaker, B., Moore, D.: Macroscopic internet topology and performance measurements from the DNS root name servers. In: USENIX LISA (2001)"},{"key":"35_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/11561071_70","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 791\u2013802. Springer, Heidelberg (2005)"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 169\u2013178 (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics and their applications. In: Proceedings of the 21th ACM Symposium on Computational Geometry (SoCG), pp. 150\u2013158 (2005)","DOI":"10.1145\/1064092.1064117"},{"key":"35_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on analysis on metric spaces","author":"J. Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on analysis on metric spaces. Springer, New York (2001)"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest-neighbors in growth-restricted metrics. In: Proceedings of the 34th annual ACM Symposium on Theory of Computing (STOC), pp. 741\u2013750 (2002)","DOI":"10.1145\/509907.510013"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"35_CR18","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithm. In: Proceedings of the International Congress of Mathematicians (ICM) (to appear, 2006)"},{"key":"35_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-27836-8_27","volume-title":"Automata, Languages and Programming","author":"E. Lebhar","year":"2004","unstructured":"Lebhar, E., Schabanel, N.: Close to optimal decentralized routing in long-range contact networks. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 294\u2013310. Springer, Heidelberg (2004)"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Naor, M., Wieder, U.: Know thy neighbor\u2019s neighbor: the power of lookahead in randomized p2p networks. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 54\u201363 (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"35_CR21","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) small-world models. In: 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 178\u2013187 (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"35_CR22","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The small world problem. Psychology Today 61(1) (1967)","DOI":"10.1037\/e400002009-005"},{"key":"35_CR23","unstructured":"Peleg, D.: Private communication (2006)"},{"key":"35_CR24","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:30Z","timestamp":1605642030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11841036_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}