Efficient dispersion in triangular grids without prior knowledge

doi:10.1016/j.tcs.2026.115810

Efficient dispersion in triangular grids without prior knowledge

2026-04-27

0

PRE

AI

DOI：10.1016/j.tcs.2026.115810

Original

Original request for help

Save

Abstract

En 中文

In the dispersion problem, a group of k <= n mobile robots, initially placed on the vertices of an anonymous graph G with n vertices, must redistribute themselves so that each vertex hosts no more than one robot. We address this challenge on an anonymous triangular grid graph, where each vertex can connect to up to six adjacent vertices. We propose a distributed deterministic root algorithm that achieves dispersion on an unoriented triangular grid graph in O( n) time, where n is the number of vertices. Each robot requires O O(log n) bits of memory. The time complexity of our algorithm and the memory usage per robot are optimal for sufficiently large k k. This work builds on previous studies by Kshemkalyani et al. [WALCOM 2020 [1]] and Banerjee et al. [ALGOWIN 2024 [2]]. Importantly, our algorithm terminates without requiring prior knowledge of n and resolves a question posed by Banerjee et al. [ALGOWIN 2024 [2]]. Additionally, our approach is generalized to rectangular triangular grids and remains robust even in the presence of robots that crash faulty.

Keywords:

Distributed algorithms

Mobile robots

Dispersion

Triangular grid

Deterministic algorithms

Efficient dispersion in triangular grids without prior knowledge

Abstract

Journal

Organization