Author name cluster

Abdullah Almethen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2023 Journal Article

Distributed transformations of Hamiltonian shapes based on line moves

Abdullah Almethen
Othon Michail
Igor Potapov

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape S I 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 S I into a given target shape S F 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 S I whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line S L. The complexity of the transformation is O ( n log 2 ⁡ n ) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

Details DOI

TCS Journal 2022 Journal Article

On efficient connectivity-preserving transformations in a grid

Abdullah Almethen
Othon Michail
Igor Potapov

We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape S I. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step, called a line move. We study the problem of transforming S I into a given connected target shape S F of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of S I and S F contain a Hamiltonian path. In particular, our transformations make O ( n log ⁡ n ) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape S I into any target connected shape S F, through a sequence of O ( n n ) moves.

Details DOI

TCS Journal 2020 Journal Article

Pushing lines helps: Efficient universal centralised transformations for programmable matter

Abdullah Almethen
Othon Michail
Igor Potapov

In this work, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all n nodes forms initially a connected shape A. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape B is also provided and the goal is to transform A into B via a sequence of line moves. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, Θ ( n 2 ) -time) universal transformations carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i. e. , sub-quadratic worst-case, transformations. This paper provides several solutions for specific and universal centralised transformations in the context of the new model. In particular we first design O ( n log ⁡ n ) -time universal transformation without preserving the connectivity of original shape. Then we focus on transformations which preserve the connectivity of the shape throughout its course and develop an O ( n n ) -time transformation for the apparently hard instance of transforming a diagonal A into a straight line B.

Details DOI