Распределённые алгоритмы на корневых неориентированных графах

Рассматриваются распределённые алгоритмы решения задач на неориентированных графах. В разделе 2 определяется используемая модель, особенностью которой является наличие корня, с которого начинается и в котором заканчивается работа алгоритма. Описываются синхронная и асинхронная разновидности модели. В разделе 3 предлагаются алгоритмы решения любых задач, основанные на сборе информации о всём графе в корне или в каждой вершине, а также, если необходимо, разметке графа (его вершин и/или рёбер). Акцент сделан на времени работы алгоритма, а при минимальном времени - на экономии памяти в вершинах и суммарном объёме пересылаемых сообщений. В остальной части статьи рассматриваются оптимизации для конкретных задач: построение максимального независимого множества (MIS - Maximal Independent Set), поиск множества всех мостов в графе (FSB - Finding Set of Bridges), построение минимального остовного дерева во взвешенном графе (MST - Minimum Spanning Tree). В разделе 4 предлагается модификация общих алгоритмов для этих задач, уменьшающая оценки размера памяти вершин и сообщений. Раздел 5 содержит нижние оценки сложности решения этих задач. В разделе 6 для синхронной модели уменьшается время работы алгоритмов с разметкой графа до нижней границы для задач с однозначным решением, зависящим только от простых циклов графа, в частности, FSB, MST и задачи поиска гальмильтонова цикла. В разделе 7 рассматриваются оптимальные по времени алгоритмы для FSB и MST для обеих моделей: синхронной и асинхронной. Заключение подводит итоги и намечает направления дальнейших исследований.