Exploration of a finite graph by a collective of agents (Q2901730)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Exploration of a finite graph by a collective of agents |
scientific article; zbMATH DE number 6062242
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Exploration of a finite graph by a collective of agents |
scientific article; zbMATH DE number 6062242 |
Statements
31 July 2012
0 references
0.94912434
0 references
0.9018218
0 references
0.8933586
0 references
0.8794583
0 references
0.87222254
0 references
0 references
0 references
0.8595774
0 references
Exploration of a finite graph by a collective of agents (English)
0 references
The exploration of a finite graph by a collective of agents is considered. Two agents (researchers) move on a graph. They can read and change marks of the graph and pass the information to the another agent (the experimenter) that builds a graph representation. An \(O(n^3)\) time and \(O(n^2)\) space algorithm that recognizes any finite non-oriented graph with \(n\) nodes is proposed. The algorithm is based on the depth-first traversal method.
0 references
