Finite graph exploration by a mobile agent
A.V. Stopkin · Mathematical Modeling and Computing · 2025
The paper considers the task of finite connected graph exploration by a mobile agent. The mobile agent moves along the graph, reads and changes marks of the graph elements, and explores the graph based on this information. A new algorithm for finite undirected graph exploration of time complexity O(n^3), space complexity O(n^2) and the upper estimate of the number of transitions along the edges made by the agent O(n^3) is proposed. For the algorithm to work, the agent needs one color. The algorithm is based on depth-first traversal method.