{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T19:57:31Z","timestamp":1771358251967,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["390859508"],"award-info":[{"award-number":["390859508"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry.<\/jats:p>\n          <jats:p>\n            To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2 - 1\/\u03b1<\/jats:sup>\n            +\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/(2\u03b1)<\/jats:sup>\n            + \u03b4\n            <jats:sub>max<\/jats:sub>\n            ) with high probability, where \u03b1 \u2208 (1\/2, 1) controls the power-law exponent of the degree distribution, and \u03b4\n            <jats:sub>max<\/jats:sub>\n            is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.\n          <\/jats:p>","DOI":"10.1145\/3516483","type":"journal-article","created":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T17:55:44Z","timestamp":1644602144000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2450-744X","authenticated-orcid":false,"given":"Thomas","family":"Bl\u00e4sius","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Baden-W\u00fcrttemberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cedric","family":"Freiberger","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Brandenburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Brandenburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9302-5527","authenticated-orcid":false,"given":"Maximilian","family":"Katzmann","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Brandenburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Montenegro-Retana","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Brandenburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marianne","family":"Thieffry","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Potsdam, Brandenburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-016-0013-0"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2020.25"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.20"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.15"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0323-3"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-88-7642-475-5_68"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.37236\/4958"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1063"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.20"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.3929\/ethz-b-000269658"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2017.20"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087829"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/2207816"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1123961"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9710-y"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M121201X"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2017.36"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553908"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2019.23"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2012.04.060"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_2_26_2","volume-title":"Random Graph Models for Complex Systems","author":"Peter Ueli","year":"2014","unstructured":"Ueli Peter. 2014. Random Graph Models for Complex Systems. Ph.D. Dissertation. ETH Z\u00fcrich."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/905464"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000103"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3516483","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3516483","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:21Z","timestamp":1750188621000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3516483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,30]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3516483"],"URL":"https:\/\/doi.org\/10.1145\/3516483","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,30]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}