Исследование графа набором автоматов.

Авторы

Бурдонов И. Б., Косачев А. С., Кулямин В. В.

Аннотация

В данной статье описан алгоритм обхода (извлечения полной информации о структуре) заранее неизвестного ориентированного графа при помощи неограниченного набора конечных автоматов, взаимодействующих при помощи обмена сообщениями и способных перемещаться вдоль дуг графа в соответствии с их ориентацией. В предположении об ограниченности времени работы базовых операций и времени пересылок отдельных сообщений общее время работы алгоритма в худшем случае ограничено O(m+nd), где n — число вершин графа, m — число его дуг, d — диаметр графа, причем эту оценку нельзя улучшить. Полные доказательства приводимых в статье утверждений опубликованы в [6]

Полный текст статьи в формате pdf

Ключевые слова

обход ориентированного графа, распределенный алгоритм, агенты-конечные автоматы

Издание

Программирование, 41(6):3-7, 2015.

Научная группа

Технологии программирования

Все публикации за 2015 год

Все публикации