Возможность и сложность распознавания графов тремя агентами

Авторы: 
Журнал: 
Страница: 
88
УДК: 
519.1
Рассматривается проблема распознавания конечных графов тремя агентами. По- строен алгоритм распознавания неориентированных графов, временная и емкостная сложности которого равны O(n2). При распознавании два агента, передвигающи- еся по графу, используют по две различные краски (всего три краски). Алгоритм основан на методе обхода графа в глубину.
info_eng: 
Problem of exploration finite graphs by three agents is considered. Constructed an algorithm for exploration undirected graphs with O(n2) (n is amount of nodes of graph) time and space complexities. Two agents (which move on graph) needs two different colors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.