{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T06:59:05Z","timestamp":1776754745295,"version":"3.51.2"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T00:00:00Z","timestamp":1500940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Grant","award":["336495 (ACDC)"],"award-info":[{"award-number":["336495 (ACDC)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,7,25]]},"DOI":"10.1145\/3087801.3087829","type":"proceedings-article","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T17:51:38Z","timestamp":1500573098000},"page":"371-380","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Greedy Routing and the Algorithmic Small-World Phenomenon"],"prefix":"10.1145","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Max-Planck-Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralph","family":"Keusch","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anisur Rahaman","family":"Molla","sequence":"additional","affiliation":[{"name":"NISER & University of Freiburg, Bhubaneswar, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129305"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"R. Albert and A.-L. Barab\u00e1si. 2002. Statistical mechanics of complex networks. Reviews of modern physics 74 1 (2002) 47.  R. Albert and A.-L. Barab\u00e1si. 2002. Statistical mechanics of complex networks. Reviews of modern physics 74 1 (2002) 47.","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature11486"},{"key":"e_1_3_2_1_6_1","unstructured":"S. Bhagat M. Burke C. Diuk I. O. Filiz and S. Edunov. 2016. Facebook Research Three and a half degrees of separation. https:\/\/research.fb.com\/three-and-a-half-degrees-of-separation\/. (2016). Accessed: 2017-02--15.  S. Bhagat M. Burke C. Diuk I. O. Filiz and S. Edunov. 2016. Facebook Research Three and a half degrees of separation. https:\/\/research.fb.com\/three-and-a-half-degrees-of-separation\/. (2016). Accessed: 2017-02--15."},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Hyperbolic Random Graphs","volume":"15","author":"Blasius T.","year":"2016","journal-title":"Separators and Treewidth. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane","volume":"16","author":"Blasius T.","year":"2016","journal-title":"European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.102.058701"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"M. Bogun\u00e1 D. Krioukov and K. C. Claffy. 2009. Navigability of complex networks. Nature Physics 5 (Jan. 2009) 74--80.  M. Bogun\u00e1 D. Krioukov and K. C. Claffy. 2009. Navigability of complex networks. Nature Physics 5 (Jan. 2009) 74--80.","DOI":"10.1038\/nphys1130"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1063"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20168"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835980.1835984"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129304"},{"key":"e_1_3_2_1_16_1","unstructured":"K. Bringmann R. Keusch and J. Lengler. 2016a. Average Distance in a General Class of Scale-Free Networks with Underlying Geometry. Preprint avaiable at arxiv:1602.05712 (2016).  K. Bringmann R. Keusch and J. Lengler. 2016a. Average Distance in a General Class of Scale-Free Networks with Underlying Geometry. Preprint avaiable at arxiv:1602.05712 (2016)."},{"key":"e_1_3_2_1_17_1","unstructured":"K. Bringmann R. Keusch and J. Lengler. 2016b. Sampling Geometric Inhomogeneous Random Graphs in Linear Time. Preprint available at arXiv:1511.00576 (2016).  K. Bringmann R. Keusch and J. Lengler. 2016b. Sampling Geometric Inhomogeneous Random Graphs in Linear Time. Preprint available at arXiv:1511.00576 (2016)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"K. Bringmann R. Keusch J. Lengler Y. Maus and A. Molla. 2017. Greedy Routing and the Algorithmic Small-World Phenomenon. Preprint available at arXiv:1612.05539 (2017).  K. Bringmann R. Keusch J. Lengler Y. Maus and A. Molla. 2017. Greedy Routing and the Algorithmic Small-World Phenomenon. Preprint available at arXiv:1612.05539 (2017).","DOI":"10.1145\/3087801.3087829"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04292"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13123-8_1"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_12"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062083"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AIHP480"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.3390\/risks3010001"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00018730110112519"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.008"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/105\/38001"},{"key":"e_1_3_2_1_30_1","unstructured":"N. Fountoulakis. 2015. On the evolution of random graphs on spaces of negative curvature. Journal of Complex Networks (2015). http:\/\/arxiv.org\/abs\/1205.2923 To appear.  N. Fountoulakis. 2015. On the evolution of random graphs on spaces of negative curvature. Journal of Complex Networks (2015). http:\/\/arxiv.org\/abs\/1205.2923 To appear."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_70"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud. 2007. Small Worlds as Navigable Augmented Networks: Model Analysis and Validation. 2--1.  P. Fraigniaud. 2007. Small Worlds as Navigable Augmented Networks: Model Analysis and Validation. 2--1.","DOI":"10.1007\/978-3-540-75520-3_2"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0137-4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806744"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0210-y"},{"key":"e_1_3_2_1_36_1","volume-title":"European Symposium on Algorithms (ESA). 376--386","author":"Fraigniaud P."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200002515"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218533"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_49"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep33441"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/11422778_95"},{"key":"e_1_3_2_1_43_1","unstructured":"M. Heydenreich T. Hulshof and J. Jorritsma. 2016. Structures in supercritical scale-free percolation. Preprint available at arXiv:1604.08180 (2016).  M. Heydenreich T. Hulshof and J. Jorritsma. 2016. Structures in supercritical scale-free percolation. Preprint available at arXiv:1604.08180 (2016)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2013.09.014"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03536-9_2"},{"key":"e_1_3_2_1_46_1","volume-title":"2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). SIAM, 26--39","author":"Kiwi M."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_3_2_1_48_1","unstructured":"J. Kleinberg. 2002. Small-world phenomena and the dynamics of information. Advances in neural information processing systems 1 (2002) 431--438.  J. Kleinberg. 2002. Small-world phenomena and the dynamics of information. Advances in neural information processing systems 1 (2002) 431--438."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.221"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019106118419"},{"key":"e_1_3_2_1_51_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP). 147:1--147:15","author":"Koch C."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273445.1273450"},{"key":"e_1_3_2_1_53_1","article-title":"Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces. SIGMETRICS Perform","author":"Krioukov D.","year":"2009","journal-title":"Eval. Rev. 37"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_44"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS.2016.7590394"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0503018102"},{"key":"e_1_3_2_1_58_1","volume-title":"36th Annual ACM Symposium on Theory of Computing (STOC). 54--63","author":"Manku G. S."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011794"},{"key":"e_1_3_2_1_60_1","first-page":"60","article-title":"The small world problem","volume":"2","author":"Milgram S.","year":"1967","journal-title":"Psychology Today"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462131"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2294052"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_2_1_65_1","unstructured":"U. Peter. 2014. Random Graph Models for Complex Systems. Ph.D. Dissertation. ETH Zurich.  U. Peter. 2014. Random Graph Models for Complex Systems. Ph.D. Dissertation. ETH Zurich."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"crossref","unstructured":"J. Postel. 1982. Simple mail transfer protocol. Information Sciences (1982).  J. Postel. 1982. Simple mail transfer protocol. Information Sciences (1982).","DOI":"10.17487\/rfc0821"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2012.08.023"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2008.12.004"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.899021"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/190"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.30.020404.104342"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts P. S. Dodds and M. E. J. Newman. 2002. Identity and search in social networks. science 296 5571 (2002) 1302--1305.  D. J. Watts P. S. Dodds and M. E. J. Newman. 2002. Identity and search in social networks. science 296 5571 (2002) 1302--1305.","DOI":"10.1126\/science.1070120"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2011.247162"}],"event":{"name":"PODC '17: ACM Symposium on Principles of Distributed Computing","location":"Washington DC USA","acronym":"PODC '17","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087829","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3087801.3087829","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:07Z","timestamp":1750217407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087829"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,25]]},"references-count":74,"alternative-id":["10.1145\/3087801.3087829","10.1145\/3087801"],"URL":"https:\/\/doi.org\/10.1145\/3087801.3087829","relation":{},"subject":[],"published":{"date-parts":[[2017,7,25]]},"assertion":[{"value":"2017-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}