graph exploration

The article addresses the problem of exploring simple undirected graphs using a multi-agent system consisting of two agents: an agent-researcher, which can traverse the graph, read and modify the labels of its elements, and exchange information with the second agent – an agent-experimenter, which constructs a map of the explored graph in its memory in the form of edge and node lists.  An algorithm is proposed with quadratic time, space, and communication complexities (with respect to the number of nodes in the graph).  The upper estimate of the number of transitions alo

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.