2026-07-22T17:45:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25207 2026-03-19T12:59:38Z ddc:004 open_access

Uniform Deployment of Mobile Robots in Complete Bipartite Graphs Shibata, Masahiro Kitamura, Naoki Eguchi, Ryota Sudo, Yuichi Nakamura, Junya Kim, Yonghwan Katayama, Yoshiaki Masuzawa, Toshimitsu Bramas, Quentin Tixeuil, Sébastien mobile robots uniform deployment complete bipartite graphs In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph K_{n,n}, which consists of two n-node sets V_L and V_R, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Masahiro Shibata and Naoki Kitamura and Ryota Eguchi and Yuichi Sudo and Junya Nakamura and Yonghwan Kim and Yoshiaki Katayama and Toshimitsu Masuzawa and Quentin Bramas and Sébastien Tixeuil 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.34 urn:nbn:de:0030-drops-252075 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.34 eng https://creativecommons.org/licenses/by/4.0/legalcode