Сборники трудов ИСП РАН


Построение прямого и обратного остовов автоматами на графе.

Игорь Бурдонов, Александр Косачев.

Аннотация

В работе представлен алгоритм параллельного исследования графа. Автомат на графе является аналогом машины Тьюринга – ячейки ленты соответствуют вершинам графа, где автомат может сохранять некоторую информацию, а движение по ленте соответствует движениям по дугам графа. Такая система может рассматриваться также как совокупность автоматов, размещенных в вершинах графа и взаимодействующих путем посылки сообщений по дугам. Каждый автомат изменяет свое состояние в соответствии с данными, сохраняемыми в вершине, а движение по дугам заменяется посылкой сообщений. Время работы предлагаемого алгоритма параллельного исследования графа ограничено сверху O(n/k+D), где n – число вершин графа, D – диаметр графа, максимальная длина простого пути (пути без самопересечений). В результате работы алгоритма строится два остова графа: прямой остов, корнем которого является корневая вершина графа, ориентированный от корня, и обратный остов, ориентированный к корню.

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

directed graphs; graph exploration, group of automata; graph spanning tree

Издание

Труды Института системного программирования РАН, том 26, вып. 6, 2014, стр. 57-62.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(6)-4

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома