6 papers
Toward Optimality: A Tighter Analysis of Message Complexity for Leader Election in Diameter-Two Networks
Abhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla
We study the message complexity of leader election in synchronous networks of diameter two. Our main contribution is a refined analysis of the randomized algorithm proposed by Chat…
Monotone Decontamination of Arbitrary Dynamic Graphs with Mobile Agents
Rajashree Bar, Daibik Barik, Adri Bhattacharya +1
Network decontamination is a well-known problem, in which the aim of the mobile agents should be to decontaminate the network (i.e., both nodes and edges). This problem comes with…
Separation of Unconscious Robots with Obstructed Visibility
Prajyot Pyati, Navjot Kaur, Saswata Jana +2
We study a recently introduced \textit{unconscious} mobile robot model, where each robot is associated with a \textit{color}, which is visible to other robots but not to itself. Th…
Time-optimal Asynchronous Minimal Vertex Covering by Myopic Robots
Saswata Jana, Subhajit Pramanick, Adri Bhattacharya +1
In a connected graph with an autonomous robot swarm with limited visibility, it is natural to ask whether the robots can be deployed to certain vertices satisfying a given property…
Perpetual exploration in anonymous synchronous networks with a Byzantine black hole
Adri Bhattacharya, Pritam Goswami, Evangelos Bampas +1
In this paper, we investigate: ``How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves malicious…
Perpetual Exploration of a Ring in Presence of Byzantine Black Hole
Pritam Goswami, Adri Bhattacharya, Raja Das +1
Perpetual exploration is a fundamental problem in the domain of mobile agents, where an agent needs to visit each node infinitely often. This issue has received lot of attention, m…