|
MATHEMATICAL MODELING AND NUMERICAL SIMULATION
Algorithm of simple graph exploration by a collective of agents
A. Stepkin, A. S. Stepkina State Higher Educational Institution “Donbass State Pedagogical University”,
19 G. Batuka st., Donetsk region, Slavyansk, 84116, Ukraine
Abstract:
The study presented in the paper is devoted to the problem of finite graph exploration using a collective of agents. Finite non-oriented graphs without loops and multiple edges are considered in this paper. The collective of agents consists of two agents-researchers, who have a finite memory independent of the number of nodes of the graph studied by them and use two colors each (three colors are used in the aggregate) and one agent-experimental, who has a finite, unlimitedly growing internal memory. Agents-researches can simultaneously traverse the graph, read and change labels of graph elements, and also transmit the necessary information to a third agent — the agent-experimenter. An agent-experimenter is a non-moving agent in whose memory the result of the functioning of agents-researchers at each step is recorded and, also, a representation of the investigated graph (initially unknown to agents) is gradually built up with a list of edges and a list of nodes.
The work includes detail describes of the operating modes of agents-researchers with an indication of the priority of their activation. The commands exchanged between agents-researchers and an agent-experimenter during the execution of procedures are considered. Problematic situations arising in the work of agents-researchers are also studied in detail, for example, staining a white vertex, when two agents simultaneously fall into the same node, or marking and examining the isthmus (edges connecting subgraphs examined by different agents-researchers), etc. The full algorithm of the agent-experimenter is presented with a detailed description of the processing of messages received from agents-researchers, on the basis of which a representation of the studied graph is built. In addition, a complete analysis of the time, space, and communication complexities of the constructed algorithm was performed.
The presented graph exploration algorithm has a quadratic (with respect to the number of nodes of the studied graph) time complexity, quadratic space complexity, and quadratic communication complexity. The graph exploration algorithm is based on the depth-first traversal method.
Keywords:
collective of agents, exploration of graphs, graph traversal.
Received: 06.07.2020 Revised: 08.11.2020 Accepted: 16.11.2020
Citation:
A. Stepkin, A. S. Stepkina, “Algorithm of simple graph exploration by a collective of agents”, Computer Research and Modeling, 13:1 (2021), 33–45
Linking options:
https://www.mathnet.ru/eng/crm868 https://www.mathnet.ru/eng/crm/v13/i1/p33
|
|