{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:33:49Z","timestamp":1762918429148,"version":"3.45.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031929342"},{"type":"electronic","value":"9783031929359"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-92935-9_10","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T04:07:26Z","timestamp":1747454846000},"page":"151-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Geographic Routing in\u00a0Fixed-Growth Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5931-771X","authenticated-orcid":false,"given":"Ofek","family":"Gila","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4410-7098","authenticated-orcid":false,"given":"Abraham M.","family":"Illickan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3549-9589","authenticated-orcid":false,"given":"Vinesh","family":"Sridhar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS\u201906), p. 75 (2006)","key":"10_CR1","DOI":"10.1109\/ICDCS.2006.72"},{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 782\u2014793 (2010)","key":"10_CR2","DOI":"10.1137\/1.9781611973075.64"},{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D.: Name independent routing for growth bounded networks. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 49\u201355 (2005)","key":"10_CR3","DOI":"10.1145\/1073970.1073978"},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/j.jalgor.2004.06.002","volume":"55","author":"Y Bartal","year":"2005","unstructured":"Bartal, Y., Mendel, M.: Randomized k-server algorithms for growth-rate bounded graphs. J. Algor. 55(2), 192\u2013202 (2005)","journal-title":"J. Algor."},{"doi-asserted-by":"crossref","unstructured":"Blum, J., Funke, S., Storandt, S.: Sublinear search spaces for shortest path planning in grid and road networks. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence. AAAI\u201918\/IAAI\u201918\/EAAI\u201918. AAAI Press (2018)","key":"10_CR5","DOI":"10.1609\/aaai.v32i1.12075"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. ACM Trans. Algor. 12(4) (2016)","key":"10_CR6","DOI":"10.1145\/2915183"},{"doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: ACM Symposium on Theory of Computing (STOC), pp. 574\u2013583 (2006)","key":"10_CR7","DOI":"10.1145\/1132516.1132599"},{"key":"10_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106397","volume":"182","author":"M Dillencourt","year":"2023","unstructured":"Dillencourt, M., Goodrich, M.T.: Simplified chernoff bounds with powers-of-two probabilities. Inf. Process. Lett. 182, 106397 (2023)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR9","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? Theor. Comput. Sci. 355(1), 96\u2013103 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1112\/S0025579300005222","volume":"12","author":"P Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s, P., Harary, F., Tutte, W.T.: On the dimension of a graph. Mathematika 12(2), 118\u2013122 (1965)","journal-title":"Mathematika"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-662-48971-0_41","volume-title":"Algorithms and Computation","author":"S Funke","year":"2015","unstructured":"Funke, S., Storandt, S.: Provable efficiency of contraction hierarchies with randomized preprocessing. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 479\u2013490. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_41"},{"doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 53\u201360 (2007)","key":"10_CR12","DOI":"10.1145\/1281100.1281111"},{"doi-asserted-by":"crossref","unstructured":"Gila, O., Goodrich, M.T., Illickan, A.M., Sridhar, V.: Fast geographic routing in fixed-growth graphs (2025)","key":"10_CR13","DOI":"10.1007\/978-3-031-92935-9_10"},{"doi-asserted-by":"publisher","unstructured":"Gila, O., Ozel, E., Goodrich, M.: Highway preferential attachment models for geographic routing. In: Combinatorial Optimization and Applications (COCOA), pp. 56\u201380. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-49614-1_4","key":"10_CR14","DOI":"10.1007\/978-3-031-49614-1_4"},{"doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Ozel, E.: Modeling the small-world phenomenon with road networks. In: 30th International Conference on Advances in Geographic Information Systems (SIGSPATIAL) (2022)","key":"10_CR15","DOI":"10.1145\/3557915.3560981"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pp. 534\u2013543 (2003)","key":"10_CR16","DOI":"10.1109\/SFCS.2003.1238226"},{"doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: ACM Symposium on Theory of Computing (STOC), pp. 741\u2013750 (2002)","key":"10_CR17","DOI":"10.1145\/509907.510013"},{"doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: ACM Symposium on Theory of Computing (STOC), pp. 163\u2013170 (2000)","key":"10_CR18","DOI":"10.1145\/335305.335325"},{"doi-asserted-by":"crossref","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Dynamic routing and location services in metrics of low doubling dimension. In: Proceedings of the 22nd International Symposium on Distributed Computing, DISC \u201908, pp. 379\u2013393. Springer-Verlag, Heidelberg (2008)","key":"10_CR19","DOI":"10.1007\/978-3-540-87779-0_26"},{"doi-asserted-by":"crossref","unstructured":"Konjevod, G., Richa, A.W., Xia, D., Yu, H.: Compact routing with slack in low doubling dimension. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 71\u201380 (2007)","key":"10_CR20","DOI":"10.1145\/1281100.1281113"},{"doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R.: The intrinsic dimensionality of graphs. In: ACM Symposium on Theory of Computing (STOC), pp. 438\u2013447 (2003)","key":"10_CR21","DOI":"10.1145\/780542.780607"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 60\u201368 (2005)","key":"10_CR22","DOI":"10.1145\/1073814.1073826"},{"doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing kleinberg\u2019s (and other) small-world models. In: ACM Symposium on Principles of Distributed Computing, pp. 179\u2013188 (2004)","key":"10_CR23","DOI":"10.1145\/1011767.1011794"},{"issue":"1","key":"10_CR24","first-page":"60","volume":"2","author":"S Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychol. Today 2(1), 60\u201367 (1967)","journal-title":"Psychol. Today"},{"doi-asserted-by":"crossref","unstructured":"Rosenberg, E.: A Survey of Fractal Dimensions of Networks, 1st edn. Springer, Heidelberg (2018)","key":"10_CR25","DOI":"10.1007\/978-3-319-90047-6_1"},{"doi-asserted-by":"crossref","unstructured":"Travers, J., Milgram, S.: An experimental study of the small world problem. In: Social Networks, pp. 179\u2013197. Elsevier (1977)","key":"10_CR26","DOI":"10.1016\/B978-0-12-442450-0.50018-3"},{"issue":"6684","key":"10_CR27","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92935-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T00:37:24Z","timestamp":1762907844000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92935-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929342","9783031929359"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92935-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}