论文标题
单一遗忘的移动代理在双向连接图中的计算能力
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs
论文作者
论文摘要
我们研究了带有存储的$ n $节点图中单个移动代理的计算能力（即节点内存）。通常，具有一位代理存储器和$ o（1）$的系统与$ O（n）$ - 位代理存储器和$ O（1）$ - 位存储一样强大。因此，我们专注于一位记忆和遗忘（即零位内存）代理之间的差异。尽管它们的计算能力不是等效的，但所有已知的结果都表现出如此差异，依赖于遗忘的代理不能将任何信息从一侧转移到整个桥边缘的另一侧。因此，我们的主要问题如下：一位记忆和遗忘代理的计算能力是否等于2边缘连接图？这项研究的主要贡献是在宽松的假设下回答这个问题，即每个节点都有$ o（\logδ）$ - 位存储（其中$δ$是图的最大程度）。我们提出了一种算法，用于使用$ o（n^2）$ - 时间间接开销的遗漏代理模拟单个单位存储器代理的任何算法。我们的结果表明，图形的拓扑结构是区分遗忘和非掩饰代理的计算能力的完全特征是桥边缘的存在。
We investigated the computational power of a single mobile agent in an $n$-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and $O(1)$-bit storage is as powerful as that with $O(n)$-bit agent memory and $O(1)$-bit storage. Thus, we focus on the difference between one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their computational powers are not equivalent, all the known results exhibiting such a difference rely on the fact that oblivious agents cannot transfer any information from one side to the other across the bridge edge. Hence, our main question is as follows: Are the computational powers of one-bit memory and oblivious agents equivalent in 2-edge-connected graphs or not? The main contribution of this study is to answer this question under the relaxed assumption that each node has $O(\logΔ)$-bit storage (where $Δ$ is the maximum degree of the graph). We present an algorithm for simulating any algorithm for a single one-bit memory agent using an oblivious agent with $O(n^2)$-time overhead per round. Our results imply that the topological structure of graphs differentiating the computational powers of oblivious and non-oblivious agents is completely characterized by the existence of bridge edges.
