|
This article is cited in 1 scientific paper (total in 1 paper)
MATHEMATICAL MODELING AND NUMERICAL SIMULATION
Using collective of agents for exploration of graph
A. Stepkin Institute of applied mathematics and mechanics of the National academy of science of Ukraine, 74 Roza Luksemburg street, Donetsk, 83114, Ukraine
Abstract:
Problem of exploration finite undirected graphs by a collective of agents is considered in this work. Two agents-researchers simultaneously move on graph, they read and change marks of graph elements, transfer the information to the agent-experimenter (it builds explored graph representation). It was constructed an algorithm linear (from amount of the graph’s nodes) time complexity, quadratic space complexity andcommunication complexity, that is equal to $O(n^2 \cdot log(n))$. Two agents (which move on graph) need two differentcolors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.
Keywords:
graph exploration, collective of agents.
Received: 13.06.2013
Citation:
A. Stepkin, “Using collective of agents for exploration of graph”, Computer Research and Modeling, 5:4 (2013), 525–532
Linking options:
https://www.mathnet.ru/eng/crm414 https://www.mathnet.ru/eng/crm/v5/i4/p525
|
Statistics & downloads: |
Abstract page: | 85 | Full-text PDF : | 23 | References: | 24 |
|