9 papers
Semi-Synchronous Exploration in Dynamic Graphs
Ashish Saxena, Anisur Rahaman Molla, Kaushik Mondal +1
We study the fundamental problem of graph exploration in dynamic graphs using mobile agents. We consider -interval connected dynamic graphs, where the topology may change arbitr…
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…
Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents
Prabhat Kumar Chand, Anisur Rahaman Molla
Mobile agents have emerged as a powerful framework for solving fundamental graph problems in distributed settings in recent times. These agents, modelled as autonomous physical or…
Agentic Distributed Computing
Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla +1
The most celebrated and extensively studied model of distributed computing is the {\em message-passing model,} in which each vertex/node of the (distributed network) graph correspo…
Optimal Dispersion Under Asynchrony
Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar +2
We study the dispersion problem in anonymous port-labeled graphs: mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an -node grap…
Computing Tree Structures in Anonymous Graphs via Mobile Agents
Prabhat Kumar Chand, Manish Kumar, Anisur Rahaman Molla
Minimum Spanning Tree (MST) and Breadth-First Search (BFS) tree constructions are classical problems in distributed computing, traditionally studied in the message-passing model, w…