License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2022.11
URN: urn:nbn:de:0030-drops-176311
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17631/
Inoue, Taichi ;
Kitamura, Naoki ;
Izumi, Taisuke ;
Masuzawa, Toshimitsu
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs
Abstract
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.
BibTeX - Entry
@InProceedings{inoue_et_al:LIPIcs.OPODIS.2022.11,
author = {Inoue, Taichi and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
title = {{Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {11:1--11:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17631},
URN = {urn:nbn:de:0030-drops-176311},
doi = {10.4230/LIPIcs.OPODIS.2022.11},
annote = {Keywords: mobile agent, depth-first search, space complexity}
}
|
Keywords: |
|
mobile agent, depth-first search, space complexity |
|
Collection: |
|
26th International Conference on Principles of Distributed Systems (OPODIS 2022) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
15.02.2023 |
