Maximal Independent Set via Mobile Agents
Debasish Pattanayak, Subhash Bhagat, Sruti Gan Chaudhuri, Anisur Rahaman Molla
Abstract
We consider the problem of finding a maximal independent set (MIS) in an unknown graph by mobile agents or mobile robots. Suppose n mobile agents are initially located at arbitrary nodes of an n-node anonymous graph G = (V, E) and the goal is that the agents autonomously relocate themselves to find a subset S ⊂ V of nodes such that S forms an MIS. The objective is to minimize both (i) the time required to find an MIS and (ii) the memory required at each agent. We consider the mobile agents with communicate-compute-move model in the synchronous setting, in which agents can communicate with other agents if they are located at the same node (called local communication).