Can I read Distance-2-Dispersion: Dispersion with Further Constraints on EtoBox?

Distance-2-Dispersion: Dispersion with Further Constraints by Kaur, Tanvir; Mondal, Kaushik is a scholarly article available to read on EtoBox.

What is Distance-2-Dispersion: Dispersion with Further Constraints about?

The aim of the dispersion problem is to place a set of $k(\leq n)$ mobile robots in the nodes of an unknown graph consisting of $n$ nodes such that in the final configuration each node contains at most one robot, starting from any arbitrary initial configuration of the robots on the graph. In this work we propose a variant of the dispersion problem where we start with any number of robots, and put an additional constraint that no two adjacent nodes contain robots in the final configuration. We name this problem as Distance-2-Dispersion (D-2-D). However, even if the number of robots $k$ is less than $n$, it may not possible for each robot to find a distinct node to reside, maintaining our added constraint. Specifically, if a maximal independent set is already formed by the nodes which contain a robot each, then other robots, if any, who are searching for a node to seat, will not find one. Hence we allow multiple robots to seat on some nodes only if there is no place to seat. If $k\geq n$, it is guaranteed that the nodes with robots form a maximal independent set of the underlying network. The graph $G=(V, E)$ has $n$ nodes and $m$ edges, where nodes are anonymous. It is a port label

Author

Kaur, Tanvir; Mondal, Kaushik

Published

2023

Language

EN