论文标题
单个代理商的自动化图探索
Self-stabilizing Graph Exploration by a Single Agent
论文作者
论文摘要
在本文中，我们提出了两种自动化算法，使单个（移动）代理探索图形。从任何初始配置开始，无论代理和所有节点的初始状态如何以及代理的初始位置，算法都可以确保代理访问所有节点。我们根据两个指标评估算法：\ emph {cover Time}，定义为访问所有节点所需的移动次数，而\ emph {memory用法}定义为维护代理和每个节点所需的存储空间。第一个算法是随机的。 Given an integer $c = Ω(n)$, its cover time is optimal, \ie $O(m)$ in expectation, and its memory requirements are $O(\log c)$ bits for the agent and $O(\log (c+δ_v))$ bits for each node $v$, where $n$ and $m$ are the numbers of nodes and edges, respectively, and $δ_v$ is the degree of node $ V $。对于一般$ c \ ge 2 $，其封面时间为$ O（m \ cdot \ min（d，\ frac {n} {c} +1，\ frac {d} {c} + \ log n））$，其中$ d $是图的直径。第二算法是确定性的。它需要一个输入整数$ k \ ge \ max（d，\ dmax）$，其中$ \ dmax $是图的最大程度。该算法的覆盖时间为$ O（m + nd）$，并且使用$ o（\ log k）$位置为代理和每个节点。
In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. Starting from any initial configuration, \ie regardless of the initial states of the agent and all nodes, as well as the initial location of the agent, the algorithms ensure the agent visits all nodes. We evaluate the algorithms based on two metrics: the \emph{cover time}, defined as the number of moves required to visit all nodes, and \emph{memory usage}, defined as the storage needed for maintaining the states of the agent and each node. The first algorithm is randomized. Given an integer $c = Ω(n)$, its cover time is optimal, \ie $O(m)$ in expectation, and its memory requirements are $O(\log c)$ bits for the agent and $O(\log (c+δ_v))$ bits for each node $v$, where $n$ and $m$ are the numbers of nodes and edges, respectively, and $δ_v$ is the degree of node $v$. For general $c \ge 2$, its cover time is $O( m \cdot \min(D, \frac{n}{c}+1, \frac{D}{c} + \log n))$, where $D$ is the diameter of a graph. The second algorithm is deterministic. It requires an input integer $k \ge \max(D, \dmax)$, where $\dmax$ is the maximum degree of the graph. The cover time of this algorithm is $O(m + nD)$, and it uses $O(\log k)$ bits of memory for both the agent and each node.
