RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2017, том 29, выпуск 5, страницы 283–310 (Mi tisp268)  

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

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

Институт системного программирования им. В.П. Иванникова РАН

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

Ключевые слова: корневой неориентированный граф, распределённые алгоритмы, задачи на графах, максимальное независимое множество, минимальное остовное дерево, поиск мостов.

DOI: https://doi.org/10.15514/ISPRAS-2017-29(5)-14

Полный текст: PDF файл (720 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: Игорь Бурдонов, Александр Косачев, Александр Сортов, “Распределённые алгоритмы на корневых неориентированных графах”, Труды ИСП РАН, 29:5 (2017), 283–310

Цитирование в формате AMSBIB
\RBibitem{BurKosSor17}
\by Игорь Бурдонов, Александр Косачев, Александр Сортов
\paper Распределённые алгоритмы на корневых неориентированных графах
\jour Труды ИСП РАН
\yr 2017
\vol 29
\issue 5
\pages 283--310
\mathnet{http://mi.mathnet.ru/tisp268}
\crossref{https://doi.org/10.15514/ISPRAS-2017-29(5)-14}
\elib{http://elibrary.ru/item.asp?id=30754474}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp268
  • http://mi.mathnet.ru/rus/tisp/v29/i5/p283

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:33
    Полный текст:6
    Литература:7

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018