{"ID":2873779,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.06064","arxiv_id":"2509.06064","title":"Gathering in Non-Vertex-Transitive Graphs Under Round Robin","abstract":"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.","short_abstract":"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 unde...","url_abs":"https://arxiv.org/abs/2509.06064","url_pdf":"https://arxiv.org/pdf/2509.06064v1","authors":"[\"Serafino Cicerone\",\"Alessia Di Fonso\",\"Gabriele Di Stefano\",\"Alfredo Navarra\"]","published":"2025-09-07T14:09:23Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"math.CO\"]","methods":"[]","has_code":false}