2025/09/07 by Serafino Cicerone, Cicerone, Serafino, Alessia Di Fonso +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Opportunistic and Delay-Tolerant Networks #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2509.06064
openalex publication_date 2025/09/07 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
The Gathering problem for a swarm of robots asks for a distributed algorithm that brings such entities to a common place, not known in advance. We consider the well-known OBLOT model with robots constrained to move along the edges of a graph, hence gathering in one vertex, eventually. Despite the classical setting under which the problem has been usually approached, we consider the `hostile' case where: i) the initial configuration may contain multiplicities, i.e. more than one robot may occupy the same vertex; ii) robots cannot detect multiplicities. As a scheduler for robot activation, we consider the "favorable" round-robin case, where robots are activated one at a time. Our objective is to achieve a complete characterization of the problem in the broad context of non-vertex-transitive graphs, i.e., graphs where the vertices are partitioned into at least two different classes of equivalence. We provide a resolution algorithm for any configuration of robots moving on such graphs, along with its correctness. Furthermore, we analyze its time complexity.