EUVIMEDEUVIMED entdecken
Crossref

Finite Undirected Graphs Exploration by a Mobile Agent

A. V. Stopkin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →