---
res:
  bibo_abstract:
  - "<jats:title>Abstract</jats:title>\r\n                  <jats:p>\r\n                    In
    this paper, we study the computation of shortest paths within the\r\n                    <jats:italic>geometric
    amoebot model</jats:italic>\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
    \                   <jats:italic>reconfigurable circuit extension</jats:italic>\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                    <jats:italic>shortest path forest problem</jats:italic>\r\n
    \                   where, given a set of\r\n                    <jats:italic>k</jats:italic>\r\n
    \                   sources and a set of\r\n                    <jats:inline-formula>\r\n
    \                     <jats:alternatives>\r\n                        <jats:tex-math>$$\\ell
    $$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n
    \                         <mml:mi>ℓ</mml:mi>\r\n                        </mml:math>\r\n
    \                     </jats:alternatives>\r\n                    </jats:inline-formula>\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                    <jats:inline-formula>\r\n
    \                     <jats:alternatives>\r\n                        <jats:tex-math>$$O(\\log
    \\ell )$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n
    \                         <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n
    \                           <mml:mo>(</mml:mo>\r\n                            <mml:mo>log</mml:mo>\r\n
    \                           <mml:mi>ℓ</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n
    \                         </mml:mrow>\r\n                        </mml:math>\r\n
    \                     </jats:alternatives>\r\n                    </jats:inline-formula>\r\n
    \                   rounds, and the second algorithm a shortest path forest for
    an arbitrary number of sources within\r\n                    <jats:inline-formula>\r\n
    \                     <jats:alternatives>\r\n                        <jats:tex-math>$$O(\\log
    n \\log ^2 k)$$</jats:tex-math>\r\n                        <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n
    \                         <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n
    \                           <mml:mo>(</mml:mo>\r\n                            <mml:mo>log</mml:mo>\r\n
    \                           <mml:mi>n</mml:mi>\r\n                            <mml:msup>\r\n
    \                             <mml:mo>log</mml:mo>\r\n                              <mml:mn>2</mml:mn>\r\n
    \                           </mml:msup>\r\n                            <mml:mi>k</mml:mi>\r\n
    \                           <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n
    \                       </mml:math>\r\n                      </jats:alternatives>\r\n
    \                   </jats:inline-formula>\r\n                    rounds. The
    former algorithm also provides an\r\n                    <jats:italic>O</jats:italic>\r\n
    \                   (1) rounds solution for the\r\n                    <jats:italic>single
    pair shortest path problem</jats:italic>\r\n                    (SPSP) and an\r\n
    \                   <jats:inline-formula>\r\n                      <jats:alternatives>\r\n
    \                       <jats:tex-math>$$O(\\log n)$$</jats:tex-math>\r\n                        <mml:math
    xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n                          <mml:mrow>\r\n
    \                           <mml:mi>O</mml:mi>\r\n                            <mml:mo>(</mml:mo>\r\n
    \                           <mml:mo>log</mml:mo>\r\n                            <mml:mi>n</mml:mi>\r\n
    \                           <mml:mo>)</mml:mo>\r\n                          </mml:mrow>\r\n
    \                       </mml:math>\r\n                      </jats:alternatives>\r\n
    \                   </jats:inline-formula>\r\n                    rounds solution
    for the\r\n                    <jats:italic>single source shortest path problem</jats:italic>\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
    \                   <jats:inline-formula>\r\n                      <jats:alternatives>\r\n
    \                       <jats:tex-math>$$O(h \\log ^3 n)$$</jats:tex-math>\r\n
    \                       <mml:math xmlns:mml=\"http://www.w3.org/1998/Math/MathML\">\r\n
    \                         <mml:mrow>\r\n                            <mml:mi>O</mml:mi>\r\n
    \                           <mml:mo>(</mml:mo>\r\n                            <mml:mi>h</mml:mi>\r\n
    \                           <mml:msup>\r\n                              <mml:mo>log</mml:mo>\r\n
    \                             <mml:mn>3</mml:mn>\r\n                            </mml:msup>\r\n
    \                           <mml:mi>n</mml:mi>\r\n                            <mml:mo>)</mml:mo>\r\n
    \                         </mml:mrow>\r\n                        </mml:math>\r\n
    \                     </jats:alternatives>\r\n                    </jats:inline-formula>\r\n
    \                   rounds w.h.p. where\r\n                    <jats:italic>h</jats:italic>\r\n
    \                   denotes the number of holes.\r\n                  </jats:p>@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Andreas
      foaf_name: Padalkin, Andreas
      foaf_surname: Padalkin
      foaf_workInfoHomepage: http://www.librecat.org/personId=88238
  - foaf_Person:
      foaf_givenName: Christian
      foaf_name: Scheideler, Christian
      foaf_surname: Scheideler
      foaf_workInfoHomepage: http://www.librecat.org/personId=20792
  bibo_doi: 10.1007/s00446-026-00505-2
  bibo_issue: '2'
  bibo_volume: 39
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0178-2770
  - http://id.crossref.org/issn/1432-0452
  dct_language: eng
  dct_publisher: Springer Science and Business Media LLC@
  dct_title: Polylogarithmic time algorithms for shortest path forests in programmable
    matter@
...