In this paper, we study the computation of shortest paths within the geometric amoebot model, 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 reconfigurable circuit extension 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 shortest path forest problem where, given a set of k sources and a set of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\ell $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(\log \ell )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(\log n \log ^2 k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <msup> <mo>log</mo> <mn>2</mn> </msup> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds. The former algorithm also provides an O(1) rounds solution for the single pair shortest path problem (SPSP) and an <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds solution for the single source shortest path problem (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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(h \log ^3 n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>h</mi> <msup> <mo>log</mo> <mn>3</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> rounds w.h.p. where h denotes the number of holes.

Polylogarithmic time algorithms for shortest path forests in programmable matter

期刊论文
出版模式：

开放获取
发表日期：

2026年4月18日

查看全文

Andreas Padalkin,
Christian Scheideler

摘要

In this paper, we study the computation of shortest paths within the geometric amoebot model, 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 reconfigurable circuit extension 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 shortest path forest problem where, given a set of k sources and a set of $\ell $ $ℓ$ 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 $O(\log \ell )$ $O (log ℓ)$ rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within $O(\log n \log ^2 k)$ $O (log n {log}^{2} k)$ rounds. The former algorithm also provides an O(1) rounds solution for the single pair shortest path problem (SPSP) and an $O(\log n)$ $O (log n)$ rounds solution for the single source shortest path problem (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 $O(h \log ^3 n)$ $O (h {log}^{3} n)$ rounds w.h.p. where h denotes the number of holes.