2026-07-23T15:38:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17631 2024-03-06T11:00:10Z ddc:004 open_access

Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs Inoue, Taichi Kitamura, Naoki Izumi, Taisuke Masuzawa, Toshimitsu mobile agent depth-first search space complexity 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²)-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Taichi Inoue and Naoki Kitamura and Taisuke Izumi and Toshimitsu Masuzawa 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.11 urn:nbn:de:0030-drops-176311 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.11 eng https://creativecommons.org/licenses/by/4.0/legalcode