论文标题
没有全球知识的移动代理的有效分散
Efficient Dispersion of Mobile Agents without Global Knowledge
论文作者
论文摘要
我们考虑移动代理的分散问题。最初，k代理位于无向图中的任意节点。代理可以同步图中的边缘从节点迁移到节点。我们的目标是让K代理位于不同的k节点，并最小化分散之前的步骤数量以及代理使用的工作记忆空间。 Kshemkalyani和Ali [ICDCN，2019年]提出了一种快速且空间有效的分散算法，假设每个代理都有全局知识，例如边缘数量和图形的最大程度。在本文中，我们提出了一种不需要这样的全局知识的色散算法，但可以保持渐近的运行时间和稍小的内存空间。
We consider the dispersion problem for mobile agents. Initially, k agents are located at arbitrary nodes in an undirected graph. Agents can migrate from node to node via an edge in the graph synchronously. Our goal is to let the k agents be located at different k nodes with minimizing the number of steps before dispersion is completed and the working memory space used by the agents. Kshemkalyani and Ali [ICDCN, 2019] present a fast and space-efficient dispersion algorithm with the assumption that each agent has global knowledge such as the number of edges and the maximum degree of a graph. In this paper, we present a dispersion algorithm that does not require such global knowledge but keeps the asymptotically same running time and slightly smaller memory space.
