Abdullah Almethen

dblp:174/2913 · DBLP profile ↗
← Back
6ranked-venue papers
6as first author
3since 2021 · last 2023
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 2 since 2021
YearPublicationVenuePosition
2023 Distributed transformations of Hamiltonian shapes based on line moves
abstract
We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape SI on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape SI into a given target shape SF via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the line formation problem. That is, starting from any shape SI whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line SL. The complexity of the transformation is O(nlog2⁡n) moves, which is asymptotically equivalent to that of the best-known centralised transformations.
Abdullah Almethen, Othon Michail, Igor Potapov
Theor. Comput. Sci.1
2022 On efficient connectivity-preserving transformations in a grid
Abdullah Almethen, Othon Michail, Igor Potapov
Theor. Comput. Sci.1
2021 Distributed Transformations of Hamiltonian Shapes Based on Line Moves
Abdullah Almethen, Othon Michail, Igor Potapov
ALGOSENSORS1
2020 On Efficient Connectivity-Preserving Transformations in a Grid
Abdullah Almethen, Othon Michail, Igor Potapov
ALGOSENSORS1
2020 Pushing lines helps: Efficient universal centralised transformations for programmable matter
Abdullah Almethen, Othon Michail, Igor Potapov
Theor. Comput. Sci.1
2019 Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter
Abdullah Almethen, Othon Michail, Igor Potapov
ALGOSENSORS1