11 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…
Black Hole Search in Dynamic Tori
Adri Bhattacharya, Giuseppe F. Italiano, Partha Sarathi Mandal
We investigate the black hole search problem by a set of mobile agents in a dynamic torus. Black hole is defined to be a dangerous stationary node which has the capability to destr…
Black Hole Search in Dynamic Cactus Graph
Adri Bhattacharya, Giuseppe F. Italiano, Partha Sarathi Mandal
We study the problem of black hole search by a set of mobile agents, where the underlying graph is a dynamic cactus. A black hole is a dangerous vertex in the graph that eliminates…
Uniform Partitioning of a Bounded Region using Opaque ASYNC Luminous Mobile Robots
Subhajit Pramanick, Saswata Jana, Adri Bhattacharya +1
We are given autonomous mobile robots inside a bounded region. The robots are opaque which means that three collinear robots are unable to see each other as one of the robots a…
Pebble guided Treasure Hunt in Plane
Adri Bhattacharya, Barun Gorain, Partha Sarathi Mandal
We study the problem of treasure hunt in a Euclidean plane by a mobile agent with the guidance of pebbles. The initial position of the agent and position of the treasure are modele…
Treasure Hunt in Graph using Pebbles
Adri Bhattacharya, Barun Gorain, Partha Sarathi Mandal
In this paper, we study the treasure hunt problem in a graph by a mobile agent. The nodes in the graph are anonymous and the edges incident to a vertex whose deg…