{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:42Z","timestamp":1787323542725,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most $O(\\log\\log n)$ are navigable. We show that for doubling dimension $\\gg\\log\\log n$, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability.<\/jats:p>","DOI":"10.1137\/06067626x","type":"journal-article","created":{"date-parts":[[2010,2,19]],"date-time":"2010-02-19T18:11:59Z","timestamp":1266603119000},"page":"72-81","source":"Crossref","is-referenced-by-count":8,"title":["A Lower Bound for Network Navigability"],"prefix":"10.1137","volume":"24","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emmanuelle","family":"Lebhar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, H. T.H. Chan, K. Dhamdhere, A. Gupta, J. M. Kleinberg, O. Neiman, and A. Slivkins,\n                      Metric embeddings with relaxed guarantees\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 2005, pp. 83\u2013100.","DOI":"10.1109\/SFCS.2005.51"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"I. Abraham and C. Gavoille,\n                      Object location using path separators\n                      , in Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2006, pp. 188\u2013197.","DOI":"10.1145\/1146381.1146411"},{"key":"R3","unstructured":"I. Abraham, C. Gavoille, A. V. Goldberg, and D. Malkhi,\n                      Routing in networks with low doubling dimension\n                      , in 26th International Conference on Distributed Computing Systems (ICDCS), IEEE Computer Society, Washington, DC, 2006."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"I. Abraham and D. Malkhi,\n                      Name independent routing for growth bounded networks\n                      , in Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), ACM, New York, 2005, pp. 49\u201355.","DOI":"10.1145\/1073970.1073978"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. Aspnes, Z. Diamadi, and G. Shah,\n                      Fault-tolerant routing in peer-to-peer systems\n                      , in Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2002, pp. 223\u2013232.","DOI":"10.1145\/571825.571862"},{"key":"R6","first-page":"429","volume":"111","author":"Assouad P.","year":"1983","journal-title":"Bull. Soc. Math."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"L. Barri\u00e8re, P. Fraigniaud, E. Kranakis, and D. Krizanc,\n                      Efficient routing in networks with long range contacts\n                      , in Proceedings of the 15th International Symposium on Distributed Computing (DISC), Lecture Notes in Comput. Sci. 2180, Springer-Verlag, New York, 2001, pp. 270\u2013284.","DOI":"10.1007\/3-540-45414-4_19"},{"key":"R8","unstructured":"H. T.H. Chan, A. Gupta, B. M. Maggs, and S. Zhou,\n                      On hierarchical routing in doubling metrics\n                      , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2005, pp. 762\u2013771."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson,\n                      Nearest-neighbor searching and metric space dimensions\n                      , in Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, T. Darrell, P. Indyk, G. Shakhnarovich, and P. Viola, eds., MIT Press, Cambridge, MA, 2006.","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"R10","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2005.12.008","volume":"355","author":"Duchon P.","year":"2006","journal-title":"Theoret. Comput. Sci., Special Issue on Complex Networks"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1126\/science.1081058"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Flammini, L. Moscardelli, A. Navarra, and S. Perennes,\n                      Asymptotically optimal solutions for small world graphs\n                      , in Proceedings of the 19th International Symposium on Distributed Computing (DISC), Lecture Notes in Comput. Sci. 3724, Springer-Verlag, New York, 2005, pp. 414\u2013428.","DOI":"10.1007\/11561927_30"},{"key":"R13","unstructured":"M. Fomenkov, K. Claffy, B. Huffaker, and D. Moore,\n                      Macroscopic internet topology and performance measurements from the dns root name servers\n                      , in USENIX LISA, San Diego, CA, 2001."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud,\n                      Greedy routing in tree-decomposed graphs: A new perspective on the small-world phenomenon\n                      , in Proceedings of the 13th Annual European Symposium on Algorithms (ESA), Mallorca, Spain, 2005, pp. 791\u2013802.","DOI":"10.1007\/11561071_70"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, C. Gavoille, and C. Paul,\n                      Eclecticism shrinks even small worlds\n                      , in Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2004, pp. 169\u2013178.","DOI":"10.1145\/1011767.1011793"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, E. Lebhar, and L. Viennot,\n                      The inframetric model for the Internet\n                      , in Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), IEEE Computer Society, Washington, DC, 2008, pp. 1759\u20131767.","DOI":"10.1109\/INFOCOM.2007.163"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. Gavoille, P. Fraigniaud, A. Kozowski, E. Lebhar, and Z. Lotker,\n                      Universal augmentation schemes for network navigability: Overcoming the sqrt(n)-barrier\n                      , in Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), ACM, New York, 2007, pp. 1\u20137.","DOI":"10.1145\/1248377.1248379"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer, and J. R. Lee,\n                      Bounded geometries, fractals, and low-distortion embeddings\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 2003, pp. 534\u2013543.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. Har-Peled and M. Mendel,\n                      Fast construction of nets in low dimensional metrics and their applications\n                      , in Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), ACM, New York, 2005, pp. 150\u2013158.","DOI":"10.1145\/1064092.1064117"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Heinonen,\n                      Lectures on Analysis on Metric Spaces\n                      , Springer-Verlag, New York, 2001.","DOI":"10.1007\/978-1-4613-0131-8"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"D. R. Karger and M. Ruhl,\n                      Finding nearest-neighbors in growth-restricted metrics\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2002, pp. 741\u2013750.","DOI":"10.1145\/509907.510013"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J. Kleinberg,\n                      The small-world phenomenon: An algorithmic perspective\n                      , in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), ACM, New York, 2000, pp. 163\u2013170.","DOI":"10.1145\/335305.335325"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J. Kleinberg,\n                      Small-world phenomena and the dynamics of information\n                      , in Proceedings of the 2001 Neural Information Processing Systems Conference, Advances in Neural Information Processing Systems (NIPS) 14, MIT Press, Cambridge, MA, 2001.","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Kleinberg,\n                      Complex networks and decentralized search algorithm\n                      , in Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, 2006, pp. 1019\u20131044.","DOI":"10.4171\/022-3\/50"},{"key":"R26","unstructured":"R. Krauthgamer and J. R. Lee,\n                      Navigating nets: Simple algorithms for proximity search\n                      , in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2004, pp. 798\u2013807."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"R. Krauthgamer and J. R. Lee,\n                      The black-box complexity of nearest neighbor search\n                      , in Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP), Turku, Finland, 2004, pp. 858\u2013869.","DOI":"10.1007\/978-3-540-27836-8_72"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor,\n                      Measured descent: A new embedding method for finite metrics\n                      , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 2004, pp. 434\u2013443.","DOI":"10.1109\/FOCS.2004.41"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg, A. Slivkins, and T. Wexler,\n                      Triangulation and embedding using small sets of beacons\n                      , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 2004, pp. 444\u2013453.","DOI":"10.1109\/FOCS.2004.70"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.019"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"G. S. Manku, M. Naor, and U. Wieder,\n                      Know thy neighbor's neighbor: The power of lookahead in randomized p2p networks\n                      , in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), ACM, New York, 2004, pp. 54\u201363.","DOI":"10.1145\/1007352.1007368"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"C. Martel and V. Nguyen,\n                      Analyzing Kleinberg's (and other) small-world models\n                      , in Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2004, pp. 178\u2013187.","DOI":"10.1145\/1011767.1011794"},{"key":"R33","first-page":"60","volume":"61","author":"Milgram S.","year":"1967","journal-title":"Psychology Today","ISSN":"https:\/\/id.crossref.org\/issn\/0033-3107","issn-type":"print"},{"key":"R34","unstructured":"D. Peleg,\n                      Private communication\n                      , 2006."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"A. Slivkins,\n                      Distance estimation and object location via rings of neighbors\n                      , in Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 2005, pp. 41\u201350.","DOI":"10.1145\/1073814.1073823"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"K. Talwar,\n                      Bypassing the embedding: Algorithms for low dimensional metrics\n                      , in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2004, pp. 281\u2013290.","DOI":"10.1145\/1007352.1007399"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/06067626X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:08:25Z","timestamp":1787321305000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/06067626X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/06067626X"],"URL":"https:\/\/doi.org\/10.1137\/06067626x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}