---
_id: '65733'
abstract:
- lang: eng
text: "Abstract\r\n \r\n In
this paper, we study the computation of shortest paths within the\r\n geometric
amoebot model\r\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\r\n
\ reconfigurable circuit extension\r\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\r\n shortest path forest problem\r\n
\ where, given a set of\r\n k\r\n
\ sources and a set of\r\n \r\n
\ \r\n $$\\ell
$$\r\n \r\n
\ ℓ\r\n \r\n
\ \r\n \r\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\r\n \r\n
\ \r\n $$O(\\log
\\ell )$$\r\n \r\n
\ \r\n O\r\n
\ (\r\n log\r\n
\ ℓ\r\n )\r\n
\ \r\n \r\n
\ \r\n \r\n
\ rounds, and the second algorithm a shortest path forest for
an arbitrary number of sources within\r\n \r\n
\ \r\n $$O(\\log
n \\log ^2 k)$$\r\n \r\n
\ \r\n O\r\n
\ (\r\n log\r\n
\ n\r\n \r\n
\ log\r\n 2\r\n
\ \r\n k\r\n
\ )\r\n \r\n
\ \r\n \r\n
\ \r\n rounds. The
former algorithm also provides an\r\n O\r\n
\ (1) rounds solution for the\r\n single
pair shortest path problem\r\n (SPSP) and an\r\n
\ \r\n \r\n
\ $$O(\\log n)$$\r\n \r\n \r\n
\ O\r\n (\r\n
\ log\r\n n\r\n
\ )\r\n \r\n
\ \r\n \r\n
\ \r\n rounds solution
for the\r\n single source shortest path problem\r\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\r\n
\ \r\n \r\n
\ $$O(h \\log ^3 n)$$\r\n
\ \r\n
\ \r\n O\r\n
\ (\r\n h\r\n
\ \r\n log\r\n
\ 3\r\n \r\n
\ n\r\n )\r\n
\ \r\n \r\n
\ \r\n \r\n
\ rounds w.h.p. where\r\n h\r\n
\ denotes the number of holes.\r\n "
article_number: '15'
author:
- first_name: Andreas
full_name: Padalkin, Andreas
id: '88238'
last_name: Padalkin
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Padalkin A, Scheideler C. Polylogarithmic time algorithms for shortest path
forests in programmable matter. Distributed Computing. 2026;39(2). doi:10.1007/s00446-026-00505-2
apa: Padalkin, A., & Scheideler, C. (2026). Polylogarithmic time algorithms
for shortest path forests in programmable matter. Distributed Computing,
39(2), Article 15. https://doi.org/10.1007/s00446-026-00505-2
bibtex: '@article{Padalkin_Scheideler_2026, title={Polylogarithmic time algorithms
for shortest path forests in programmable matter}, volume={39}, DOI={10.1007/s00446-026-00505-2},
number={215}, journal={Distributed Computing}, publisher={Springer Science and
Business Media LLC}, author={Padalkin, Andreas and Scheideler, Christian}, year={2026}
}'
chicago: Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms
for Shortest Path Forests in Programmable Matter.” Distributed Computing
39, no. 2 (2026). https://doi.org/10.1007/s00446-026-00505-2.
ieee: 'A. Padalkin and C. Scheideler, “Polylogarithmic time algorithms for shortest
path forests in programmable matter,” Distributed Computing, vol. 39, no.
2, Art. no. 15, 2026, doi: 10.1007/s00446-026-00505-2.'
mla: Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms
for Shortest Path Forests in Programmable Matter.” Distributed Computing,
vol. 39, no. 2, 15, Springer Science and Business Media LLC, 2026, doi:10.1007/s00446-026-00505-2.
short: A. Padalkin, C. Scheideler, Distributed Computing 39 (2026).
date_created: 2026-05-29T12:11:32Z
date_updated: 2026-05-29T12:13:09Z
department:
- _id: '34'
- _id: '7'
- _id: '79'
doi: 10.1007/s00446-026-00505-2
intvolume: ' 39'
issue: '2'
language:
- iso: eng
publication: Distributed Computing
publication_identifier:
issn:
- 0178-2770
- 1432-0452
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Polylogarithmic time algorithms for shortest path forests in programmable matter
type: journal_article
user_id: '15578'
volume: 39
year: '2026'
...