{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T06:05:01Z","timestamp":1779602701981,"version":"3.53.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032264640","type":"print"},{"value":"9783032264657","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-26465-7_19","type":"book-chapter","created":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:52:03Z","timestamp":1779601923000},"page":"351-370","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Distributed Computation of\u00a0Compact Routing Schemes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8852-5182","authenticated-orcid":false,"given":"Jinfeng","family":"Dou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9798-6993","authenticated-orcid":false,"given":"Thorsten","family":"G\u00f6tte","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7029-0014","authenticated-orcid":false,"given":"Henning","family":"Hillebrandt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5278-528X","authenticated-orcid":false,"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5110-5625","authenticated-orcid":false,"given":"Julian","family":"Werthmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,24]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Ruppert, E., Malkhi, D. (eds.) Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, 23\u201326 July 2006. pp. 188\u2013197. ACM (2006). https:\/\/doi.org\/10.1145\/1146381.1146411","DOI":"10.1145\/1146381.1146411"},{"key":"19_CR2","doi-asserted-by":"publisher","unstructured":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P.: Shortest paths in a hybrid network model. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020. pp. 1280\u20131299. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.78","DOI":"10.1137\/1.9781611975994.78"},{"issue":"5\u20136","key":"19_CR3","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput. 22(5\u20136), 363\u2013379 (2010). https:\/\/doi.org\/10.1007\/s00446-009-0088-2","journal-title":"Distrib. Comput."},{"key":"19_CR4","doi-asserted-by":"publisher","unstructured":"Baswana, S., Sen, S.: Simple algorithms for spanners in weighted graphs. In: Encyclopedia of Algorithms, pp. 1981\u20131986. Springer, New York (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_10","DOI":"10.1007\/978-1-4939-2864-4_10"},{"key":"19_CR5","doi-asserted-by":"publisher","unstructured":"Blelloch, G.E., Gu, Y., Shun, J., Sun, Y.: Parallelism in randomized incremental algorithms. J. ACM 67(5), 27:1\u201327:27 (2020). https:\/\/doi.org\/10.1145\/3402819","DOI":"10.1145\/3402819"},{"key":"19_CR6","doi-asserted-by":"publisher","unstructured":"Castenow, J., Kolb, C., Scheideler, C.: A bounding box overlay for competitive routing in hybrid communication networks. In: Mukherjee, N., Pemmaraju, S.V. (eds.) 21st International Conference on Distributed Computing and Networking, ICDCN 2020, Kolkata, India, 4\u20137 January 2020, pp. 14:1\u201314:10. ACM (2020). https:\/\/doi.org\/10.1145\/3369740.3369777","DOI":"10.1145\/3369740.3369777"},{"key":"19_CR7","doi-asserted-by":"publisher","unstructured":"Coy, S., Czumaj, A., Scheideler, C., Schneider, P., Werthmann, J.: Routing schemes for hybrid communication networks. In: Rajsbaum, S., Balliu, A., Daymude, J.J., Olivetti, D. (eds.) Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings. LNCS, Alcal\u00e1 de Henares, Spain, 6\u20139 June 2023, vol. 13892, pp. 317\u2013338. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-32733-9_14","DOI":"10.1007\/978-3-031-32733-9_14"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-642-14553-7_25","volume-title":"Frontiers in Algorithmics","author":"E Diot","year":"2010","unstructured":"Diot, E., Gavoille, C.: Path separability of graphs. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 262\u2013273. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14553-7_25"},{"key":"19_CR9","doi-asserted-by":"publisher","unstructured":"Dou, J., G\u00f6tte, T., Hillebrandt, H., Scheideler, C., Werthmann, J.: Brief announcement: Distributed construction of near-optimal compact routing schemes for planar graphs. In: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, 19\u201323 June 2023, pp. 67\u201370. ACM (2023). https:\/\/doi.org\/10.1145\/3583668.3594561","DOI":"10.1145\/3583668.3594561"},{"key":"19_CR10","doi-asserted-by":"publisher","unstructured":"Dou, J., G\u00f6tte, T., Hillebrandt, H., Scheideler, C., Werthmann, J.: Distributed and parallel low-diameter decompositions for arbitrary and restricted graphs. In: 16th Innovations in Theoretical Computer Science Conference, ITCS 2025. LIPIcs, 7\u201310 January 2025, Columbia University, New York, NY, USA, vol.\u00a0325, pp. 45:1\u201345:26. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2025.45","DOI":"10.4230\/LIPICS.ITCS.2025.45"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Dou, J., G\u00f6tte, T., Hillebrandt, H., Scheideler, C., Werthmann, J.: Distributed construction of near-optimal compact routing schemes for planar graphs (2023). https:\/\/arxiv.org\/abs\/2305.02854","DOI":"10.1145\/3583668.3594561"},{"key":"19_CR12","doi-asserted-by":"publisher","unstructured":"Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes: extended abstract. In: Giakkoupis, G. (ed.) Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, 25\u201328 July 2016, pp. 235\u2013244. ACM (2016). https:\/\/doi.org\/10.1145\/2933057.2933098","DOI":"10.1145\/2933057.2933098"},{"key":"19_CR13","doi-asserted-by":"publisher","unstructured":"Elkin, M., Neiman, O.: Near-optimal distributed routing with low memory. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC \u201918, pp. 207\u2013216, Association for Computing Machinery, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3212734.3212761","DOI":"10.1145\/3212734.3212761"},{"key":"19_CR14","doi-asserted-by":"publisher","unstructured":"Elkin, M., Neiman, O.: Efficient algorithms for constructing very sparse spanners and emulators. ACM Trans. Algorithms 15(1), 4:1\u20134:29 (2019). https:\/\/doi.org\/10.1145\/3274651","DOI":"10.1145\/3274651"},{"key":"19_CR15","unstructured":"Feldmann, M., Hinnenthal, K., Scheideler, C.: Fast hybrid network algorithms for shortest paths in sparse graphs. In: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), pp. 31:1\u201331:16 (2020)"},{"key":"19_CR16","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks I: planar embedding. In: Giakkoupis, G. (ed.) Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, 25\u201328 July 2016, pp. 29\u201338. ACM (2016). https:\/\/doi.org\/10.1145\/2933057.2933109","DOI":"10.1145\/2933057.2933109"},{"key":"19_CR17","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and Min-Cut. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January 2016, pp. 202\u2013219. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch16","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"19_CR18","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Haeupler, B., Zuzic, G.: Hop-constrained oblivious routing. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Italy, June 2021, pp. 1208\u20131220. ACM (2021). https:\/\/doi.org\/10.1145\/3406325.3451098","DOI":"10.1145\/3406325.3451098"},{"key":"19_CR19","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Zuzic, G.: Universally-optimal distributed exact Min-Cut. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, Salerno Italy, July 2022, pp. 281\u2013291. ACM (2022). https:\/\/doi.org\/10.1145\/3519270.3538429","DOI":"10.1145\/3519270.3538429"},{"key":"19_CR20","doi-asserted-by":"publisher","unstructured":"Harb, E., Huang, Z., Zheng, D.W.: Shortest path separators in unit disk graphs. In: Chan, T., Fischer, J., Iacono, J., Herman, G. (eds.) 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0308, pp. 66:1\u201366:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2024). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2024.66","DOI":"10.4230\/LIPIcs.ESA.2024.66"},{"key":"19_CR21","unstructured":"Hillebrandt, H.: Verteiltes Berechnen kompakter Routingtabellen in Unit Disk Graphen. Bachelor\u2019s thesis, Paderborn University (2022)"},{"key":"19_CR22","doi-asserted-by":"publisher","unstructured":"Izumi, T., Kitamura, N., Naruse, T., Schwartzman, G.: Fully polynomial-time distributed computation in low-treewidth graphs. In: Agrawal, K., Lee, I.A. (eds.) SPAA \u201922: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, 11\u201314 July 2022, pp. 11\u201322. ACM (2022). https:\/\/doi.org\/10.1145\/3490148.3538590","DOI":"10.1145\/3490148.3538590"},{"key":"19_CR23","doi-asserted-by":"publisher","unstructured":"Jauregui, B., Montealegre, P., Rapaport, I.: Deterministic distributed DFS via cycle separators in planar graphs. In: Balliu, A., Kuhn, F. (eds.) Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, Hotel Las Brisas Huatulco, Huatulco, Mexico, 16\u201320 June 2025, pp. 268\u2013277. ACM (2025). https:\/\/doi.org\/10.1145\/3732772.3733558","DOI":"10.1145\/3732772.3733558"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"Jung, D., Kolb, C., Scheideler, C., Sundermeier, J.: Competitive routing in hybrid communication networks. In: Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Revised Selected Papers, Helsinki, Finland, 23\u201324 August 2018, pp. 15\u201331 (2018)","DOI":"10.1007\/978-3-030-14094-6_2"},{"key":"19_CR25","doi-asserted-by":"publisher","unstructured":"Kao, M.Y., Teng, S.H., Toyama, K.: Improved parallel depth-first search in undirected planar graphs. In: Goos, G., Hartmanis, J., Dehne, F., Sack, J.R., Santoro, N., Whitesides, S. (eds.) Algorithms and Data Structures. LNCS, vol.\u00a0709, pp. 409\u2013420. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57155-8_266","DOI":"10.1007\/3-540-57155-8_266"},{"key":"19_CR26","doi-asserted-by":"publisher","unstructured":"Kuhn, F., Schneider, P.: Routing schemes and distance oracles in the hybrid model. In: Scheideler, C. (ed.) 36th International Symposium on Distributed Computing, DISC 2022. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0246, pp. 28:1\u201328:22. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2022.28","DOI":"10.4230\/LIPIcs.DISC.2022.28"},{"key":"19_CR27","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages: extended abstract. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 381\u2013390 (2013). https:\/\/doi.org\/10.1145\/2488608.2488656","DOI":"10.1145\/2488608.2488656"},{"key":"19_CR28","doi-asserted-by":"publisher","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Georgiou, C., Spirakis, P.G. (eds.) Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, 21\u201323 July 2015, pp. 153\u2013162. ACM (2015). https:\/\/doi.org\/10.1145\/2767386.2767398","DOI":"10.1145\/2767386.2767398"},{"issue":"2","key":"19_CR29","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00446-018-0326-6","volume":"32","author":"C Lenzen","year":"2018","unstructured":"Lenzen, C., Patt-Shamir, B., Peleg, D.: Distributed distance computation and routing with small messages. Distrib. Comput. 32(2), 133\u2013157 (2018). https:\/\/doi.org\/10.1007\/s00446-018-0326-6","journal-title":"Distrib. Comput."},{"key":"19_CR30","doi-asserted-by":"publisher","unstructured":"Li, J., Parter, M.: Planar diameter via metric compression. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23\u201326 June 2019, pp. 152\u2013163. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316358","DOI":"10.1145\/3313276.3316358"},{"issue":"10","key":"19_CR31","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/TPDS.2003.1239871","volume":"14","author":"XY Li","year":"2003","unstructured":"Li, X.Y., Calinescu, G., Wan, P.J., Wang, Y.: Localized Delaunay triangulation with application in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 14(10), 1035\u20131047 (2003). https:\/\/doi.org\/10.1109\/TPDS.2003.1239871","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"4","key":"19_CR32","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986). https:\/\/doi.org\/10.1137\/0215074","journal-title":"SIAM J. Comput."},{"key":"19_CR33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA (2000)"},{"key":"19_CR34","doi-asserted-by":"publisher","unstructured":"Rozhon, V., Grunau, C., Haeupler, B., Zuzic, G., Li, J.: Undirected (1+$$\\epsilon $$)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In: Leonardi, S., Gupta, A. (eds.) STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, 20\u201324 June 2022, pp. 478\u2013487. ACM (2022). https:\/\/doi.org\/10.1145\/3519935.3520074","DOI":"10.1145\/3519935.3520074"},{"key":"19_CR35","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004). https:\/\/doi.org\/10.1145\/1039488.1039493","DOI":"10.1145\/1039488.1039493"},{"key":"19_CR36","doi-asserted-by":"publisher","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Rosenberg, A.L. (ed.) Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, 4\u20136 July 2001, pp. 1\u201310. ACM (2001). https:\/\/doi.org\/10.1145\/378580.378581","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-26465-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:52:05Z","timestamp":1779601925000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-26465-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032264640","9783032264657"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-26465-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"24 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Durham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"33","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2026.webspace.durham.ac.uk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}