Book
Open access
Sep 2026
Asynchronous Dispersion with Optimal Time Complexity
We study the dispersion problem for k mobile agents on an n-node anonymous graph with memory-less nodes and maximum degree Δ. Agents must autonomously relocate so that no two agents occupy the same node. While an optimal O(k)-time, O(log (k + Δ))-memory algorithm is known under synchronous settings, the best known asyn...
Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar et al.
· Proceedings of the Internati... · 1 citation