{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:46:46Z","timestamp":1782697606307,"version":"3.54.5"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T00:00:00Z","timestamp":1776470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T00:00:00Z","timestamp":1776470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SCHE 1592\/10-1"],"award-info":[{"award-number":["SCHE 1592\/10-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n In this paper, we study the computation of shortest paths within the\n geometric amoebot model<\/jats:italic>\n , a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in many different contexts. We consider the\n reconfigurable circuit extension<\/jats:italic>\n of the model where the amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots. We propose distributed algorithms for the\n shortest path forest problem<\/jats:italic>\n where, given a set of\n k<\/jats:italic>\n sources and a set of\n \n \n $$\\ell $$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n destinations, the amoebot structure has to compute a forest that connects each destination to its closest source on a shortest path. Our main results are two algorithms for hole-free structures. The first algorithm constructs a shortest path tree for a single source within\n \n \n $$O(\\log \\ell )$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n \u2113<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within\n \n \n $$O(\\log n \\log ^2 k)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds. The former algorithm also provides an\n O<\/jats:italic>\n (1) rounds solution for the\n single pair shortest path problem<\/jats:italic>\n (SPSP) and an\n \n \n $$O(\\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds solution for the\n single source shortest path problem<\/jats:italic>\n (SSSP) since these problems are special cases of the considered problem. Then, we adapt the latter algorithm to an offset version of the problem. This allows us to solve the problem for amoebot structures with holes within\n \n \n $$O(h \\log ^3 n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n h<\/mml:mi>\n \n log<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds w.h.p. where\n h<\/jats:italic>\n denotes the number of holes.\n <\/jats:p>","DOI":"10.1007\/s00446-026-00505-2","type":"journal-article","created":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T03:14:13Z","timestamp":1776482053000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polylogarithmic time algorithms for shortest path forests in programmable matter"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4601-9597","authenticated-orcid":false,"given":"Andreas","family":"Padalkin","sequence":"first","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"}]}],"member":"297","published-online":{"date-parts":[[2026,4,18]]},"reference":[{"issue":"2","key":"505_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1142\/S0129053393000086","volume":"5","author":"T Toffoli","year":"1993","unstructured":"Toffoli, T., Margolus, N.: Programmable Matter: Concepts and Realization. Int J High Speed Comput. 5(2), 155\u2013170 (1993)","journal-title":"Int J High Speed Comput."},{"issue":"14","key":"505_CR2","doi-asserted-by":"publisher","first-page":"2297","DOI":"10.3390\/polym13142297","volume":"13","author":"S An","year":"2021","unstructured":"An, S., Yoon, S.S., Lee, M.W.: Self-healing structural materials. Polymers 13(14), 2297 (2021)","journal-title":"Polymers"},{"issue":"3","key":"505_CR3","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1088\/0957-4484\/10\/3\/301","volume":"10","author":"C Montemagno","year":"1999","unstructured":"Montemagno, C., Bachand, G.: Constructing nanomechanical devices powered by biomolecular motors. Nanotechnology 10(3), 225 (1999)","journal-title":"Nanotechnology"},{"issue":"4","key":"505_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1089\/cmb.2021.0363","volume":"29","author":"M Feldmann","year":"2022","unstructured":"Feldmann, M., Padalkin, A., Scheideler, C., Dolev, S.: Coordinating Amoebots via Reconfigurable Circuits. J. Comput. Biol. 29(4), 317\u2013343 (2022)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"505_CR5","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/s11047-024-09981-6","volume":"23","author":"A Padalkin","year":"2024","unstructured":"Padalkin, A., Scheideler, C., Warner, D.: The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4), 603\u2013625 (2024)","journal-title":"Nat. Comput."},{"key":"505_CR6","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal Shape Formation for Programmable Matter. In: SPAA. ACM; (2016). p. 289\u2013299","DOI":"10.1145\/2935764.2935784"},{"issue":"1","key":"505_CR7","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00446-019-00350-6","volume":"33","author":"GA Di Luna","year":"2020","unstructured":"Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distributed Comput. 33(1), 69\u2013101 (2020)","journal-title":"Distributed Comput."},{"key":"505_CR8","unstructured":"Kostitsyna, I., Peters, T., Speckmann, B.: Fast Reconfiguration for Programmable Matter. In: DISC. vol. 281 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; (2023). p. 27:1\u201327:21"},{"key":"505_CR9","doi-asserted-by":"crossref","unstructured":"Daymude, J.J., Richa, A.W., Weber, J.W.: Bio-Inspired Energy Distribution for Programmable Matter. In: ICDCN. ACM; 2021. p. 86\u201395","DOI":"10.1145\/3427796.3427835"},{"key":"505_CR10","unstructured":"Weber, J.W., Chhabra, T., Richa, A.W., Daymude, J.J.: Energy-Constrained Programmable Matter Under Unfair Adversaries. OPODIS, LIPIcs, vol. 286, pp. 7:1\u20137:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"505_CR11","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: amoebot - a new model for programmable matter. In: SPAA. ACM; (2014). p. 220\u2013222","DOI":"10.1145\/2612669.2612712"},{"issue":"2","key":"505_CR12","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00446-023-00443-3","volume":"36","author":"JJ Daymude","year":"2023","unstructured":"Daymude, J.J., Richa, A.W., Scheideler, C.: The canonical amoebot model: algorithms and concurrency control. Distributed Comput. 36(2), 159\u2013192 (2023)","journal-title":"Distributed Comput."},{"issue":"6","key":"505_CR13","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1006\/cgip.1993.1039","volume":"55","author":"K Sugihara","year":"1993","unstructured":"Sugihara, K.: Approximation of Generalized Voronoi Diagrams by Ordinary Voronoi Diagrams. CVGIP Graph Model Image Process. 55(6), 522\u2013531 (1993)","journal-title":"CVGIP Graph Model Image Process."},{"key":"505_CR14","unstructured":"Artmann, M., Padalkin, A., Scheideler, C.: On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. In: DISC. vol. 356 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2025. p. 7:1\u20137:22"},{"key":"505_CR15","unstructured":"Emek, Y., Gil, Y., Harlev, N.: On the Power of Graphical Reconfigurable Circuits. In: DISC. vol. 319 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; (2024). p. 22:1\u201322:16"},{"key":"505_CR16","doi-asserted-by":"crossref","unstructured":"Almalki, N., Gupta, S., Michail, O., Padalkin, A.: Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits. In: SAND. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2025. To appear","DOI":"10.1007\/978-3-032-11127-2_5"},{"key":"505_CR17","unstructured":"Kostitsyna, I., Peters, T., Speckmann, B.: Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter. In: DISC. vol. 246 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2022. p. 47:1\u201347:3"},{"issue":"4","key":"505_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00446-021-00412-8","volume":"35","author":"S Chechik","year":"2022","unstructured":"Chechik, S., Mukhtar, D.: Single-source shortest paths in the CONGEST model with improved bounds. Distributed Comput. 35(4), 357\u2013374 (2022)","journal-title":"Distributed Comput."},{"issue":"2","key":"505_CR19","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"505_CR20","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., et al.: Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"505_CR21","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Nanongkai, D.: Distributed exact weighted all-pairs shortest paths in near-linear time. In: STOC. ACM; (2019). p. 334\u2013342","DOI":"10.1145\/3313276.3316326"},{"key":"505_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages: extended abstract. In: STOC. ACM; (2013). p. 381\u2013390","DOI":"10.1145\/2488608.2488656"},{"key":"505_CR23","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: STOC. ACM; (2014). p. 565\u2013573","DOI":"10.1145\/2591796.2591850"},{"key":"505_CR24","doi-asserted-by":"crossref","unstructured":"Augustine, J., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P.: Shortest Paths in a Hybrid Network Model. In: SODA. SIAM; (2020). p. 1280\u20131299","DOI":"10.1137\/1.9781611975994.78"},{"key":"505_CR25","unstructured":"Censor-Hillel, K., Leitersdorf, D., Polosukhin, V.: Distance Computations in the Hybrid Network Model via Oracle Simulations. In: STACS. vol. 187 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2021. p. 21:1\u201321:19"},{"key":"505_CR26","unstructured":"Feldmann, M., Hinnenthal, K., Scheideler, C.: Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs. In: OPODIS. vol. 184 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2020. p. 31:1\u201331:16"},{"key":"505_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.114352","volume":"985","author":"S Coy","year":"2024","unstructured":"Coy, S., Czumaj, A., Scheideler, C., Schneider, P., Werthmann, J.: Routing schemes for hybrid communication networks. Theor. Comput. Sci. 985, 114352 (2024). https:\/\/doi.org\/10.1016\/J.TCS.2023.114352","journal-title":"Theor. Comput. Sci."},{"key":"505_CR28","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Schneider, P.: Computing Shortest Paths and Diameter in the Hybrid Network Model. In: PODC. ACM; (2020). p. 109\u2013118","DOI":"10.1145\/3382734.3405719"},{"key":"505_CR29","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Kuhn, F.: Deploying Wireless Networks with Beeps. In: DISC. vol. 6343 of Lecture Notes in Computer Science. Springer; (2010). p. 148\u2013162","DOI":"10.1007\/978-3-642-15763-9_15"},{"key":"505_CR30","unstructured":"Dufoulon, F., Emek, Y., Gelles, R.: Beeping Shortest Paths via Hypergraph Bipartite Decomposition. In: ITCS. vol. 251 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; (2023). p. 45:1\u201345:24"},{"key":"505_CR31","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Vishkin, U.: An Efficient Parallel Biconnectivity Algorithm. SIAM J. Comput. 14(4), 862\u2013874 (1985)","DOI":"10.1137\/0214061"},{"key":"505_CR32","doi-asserted-by":"crossref","unstructured":"Cong, G., Bader, D.A.: The Euler Tour Technique and Parallel Rooted Spanning Tree. In: ICPP. IEEE Computer Society; (2004). p. 448\u2013457","DOI":"10.1109\/ICPP.2004.1327954"},{"key":"505_CR33","first-page":"185","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages de lignes. Journal f\u00fcr die reine und angewandte Mathematik. 70, 185\u2013190 (1869)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik."},{"issue":"2","key":"505_CR34","first-page":"27","volume":"12","author":"H Bielak","year":"2012","unstructured":"Bielak, H., Panczyk, M.: A self-stabilizing algorithm for finding weighted centroid in trees. Ann UMCS Informatica. 12(2), 27\u201337 (2012)","journal-title":"Ann UMCS Informatica."},{"key":"505_CR35","doi-asserted-by":"crossref","unstructured":"Padalkin, A., Scheideler, C.: Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. In: PODC. ACM; (2024). p. 65\u201375","DOI":"10.1145\/3662158.3662776"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00505-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-026-00505-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00505-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T01:39:42Z","timestamp":1782697182000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-026-00505-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,18]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["505"],"URL":"https:\/\/doi.org\/10.1007\/s00446-026-00505-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,18]]},"assertion":[{"value":"31 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"15"}}