Distance-2-Dispersion with Termination by a Strong Team

Distance-2-Dispersion (D-2-D) problem aims to disperse k mobile robots starting from an arbitrary initial configuration on an anonymous port-labeled graph G with n nodes such that no two robots occupy adjacent nodes in the final configuration, though multiple robots may occupy a single node if there is no other empty node whose all adjacent nodes are also empty. In the existing literature, this problem is solved starting from a rooted configuration for \(k(\ge 1)\) robots using \(O(m\varDelta )\) synchronous rounds with a total of \(O(\log n)\) memory per robot, where m is the number of edges and \(\varDelta \) is the maximum degree of the graph. In this work, we start with \(k>n\) mobile robots and improve the run time to O(m) starting from a rooted configuration using the same amount of memory per robot. Further, we achieve D-2-D for an arbitrary initial configuration in O(pm) rounds using \(O(\log n)\) memory per robot, where p is the number of nodes containing robots in the initial configuration. Both the algorithms terminate without any global knowledge of \(m,n,\varDelta ,k,p\) . As we start with \(k>n\) robots, the nodes occupied by robots in the final configuration form a maximal independent set of the graph.