mobile agent

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 t

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.