Стёпкин А. В.

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

Авторы: 
Журнал: 
Страница: 
88
Рассматривается проблема распознавания конечных графов тремя агентами. По- строен алгоритм распознавания неориентированных графов, временная и емкостная сложности которого равны O(n2). При распознавании два агента, передвигающи- еся по графу, используют по две различные краски (всего три краски). Алгоритм основан на методе обхода графа в глубину.