Gathering in Non-Vertex-Transitive Graphs Under Round Robin
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915483924561920 |
|---|---|
| author | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| author_facet | Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06064 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gathering in Non-Vertex-Transitive Graphs Under Round Robin Cicerone, Serafino Di Fonso, Alessia Di Stefano, Gabriele Navarra, Alfredo Distributed, Parallel, and Cluster Computing Combinatorics 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. |
| title | Gathering in Non-Vertex-Transitive Graphs Under Round Robin |
| topic | Distributed, Parallel, and Cluster Computing Combinatorics |
| url | https://arxiv.org/abs/2509.06064 |