Finite Undirected Graphs Exploration by a Mobile Agent
Mathematical Modeling and Computing · 2026 · 13 (1) · 225-231
DOI: 10.23939/mmc2026.01.225 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Modeling and Computing, 2026. Verfasst von A. V. Stopkin. Die Arbeit nennt 19 Literaturangaben.
Abstract (Originalsprache)
Since any environment can be represented as a graph, the problem of graph exploration remains highly relevant. This paper investigates the exploration of finite, connected, simple, and undirected graphs by a mobile agent. A new graph exploration method is proposed, along with an algorithm that enables the mobile agent to traverse the graph, read and modify labels of its elements, and incrementally reconstruct the graph structure in its memory. The algorithm is based on the depth-first search approach and uses an implicit node numbering technique. It is proven that the graph reconstructed by the mobile agent is isomorphic to the explored graph. The proposed algorithm has quadratic time and space complexities with respect to the number of nodes. The number of required edge transitions is also estimated to be quadratic. The algorithm operates using paint of a single color.
Zitieren
APA
Stopkin, A. V. (2026). Finite Undirected Graphs Exploration by a Mobile Agent. Mathematical Modeling and Computing, 13(1), 225-231. https://doi.org/10.23939/mmc2026.01.225
Vancouver
Stopkin AV. Finite Undirected Graphs Exploration by a Mobile Agent. Mathematical Modeling and Computing. 2026;13(1):225-231. doi:10.23939/mmc2026.01.225
BibTeX
@article{Stopkin2026,
author = {Stopkin, A. V.},
title = {Finite Undirected Graphs Exploration by a Mobile Agent},
journal = {Mathematical Modeling and Computing},
year = {2026},
volume = {13},
number = {1},
pages = {225--231},
doi = {10.23939/mmc2026.01.225}
}
EUVIMED