Filling MIS Vertices by Myopic Luminous Robots
share
We present the problem of finding a maximal independent set (MIS) (named as MIS Filling problem) of an arbitrary connected graph having n vertices with luminous myopic mobile robots. The robots enter the graph one after another from a particular vertex called the Door and disperse along the edges of the graph without collision to occupy vertices such that the set of vertices occupied by the robots is a maximal independent set. We assume the robots have knowledge only about the maximum degree of the graph, denoted by Δ. In this paper, we explore two versions of the problem: the solution to the first version, named as MIS Filling with Single Door, works under an asynchronous scheduler using robots with 3 hops of visibility range, Δ + 6 number of colors and O(logΔ) bits of persistent storage. The time complexity is measured in terms of epochs and it can be solved in O(n^2) epochs. An epoch is the smallest time interval in which each participating robot gets activated and executes the algorithm at least once. For the second version with k ( > 1) Doors, named as MIS Filling with Multiple Doors, the solution works under a semi-synchronous scheduler using robots with 5 hops of visibility range, Δ + k + 6 number of colors and O(log (Δ + k)) bits of persistent storage. The problem with multiple Doors can be solved in O(n^2) epochs.
READ FULL TEXT