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

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

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



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






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


Труды ИСП РАН, 2015, том 27, выпуск 1, страницы 69–96 (Mi tisp114)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Мониторинг динамически меняющегося графа

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

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

Аннотация: Исследование ориентированных графов является корневой задачей во многих приложениях. Такое исследование имеет особую специфику тогда, когда граф моделирует сеть связи, в том числе сеть интернета и GRID. Узел сети имеет локальную информацию о сети: он «знает» только о дугах, выходящих из этой вершины, но «не знает», куда (в какие вершины) эти дуги ведут. Узлы сети обмениваются сообщениями, передаваемыми по сетевым связям, которые в графе изображаются как дуги и играют роль каналов передачи сообщений. Исследование графа базируется на его обходе, когда сообщение проходит по каждой дуге графа. Пока не пройдена какая-то дуга, нет уверенности, что она не ведёт в ещё не исследованную часть графа. Обычно рассматривается обход графа с помощью одного сообщения, циркулирующего в сети. Обход выполняется быстрее, если выполнять его параллельно: по сети одновременно циркулирует не одно, а множество сообщений. В данной работе рассматривается параллельное исследование сильно связного графа, целью которого является не просто обход графа, а сбор полной информации о графе в каждой его вершине. Вторая особенность работы — исследование динамически меняющегося графа: его дуги могут исчезать, появляться или менять свои конечные вершины. Предлагается алгоритм работы автоматов, который обеспечивает сбор полной информации о графе в каждой вершине графа.

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

DOI: https://doi.org/10.15514/ISPRAS-2015-27(1)-5

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

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

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

Образец цитирования: Игорь Бурдонов, Александр Косачев, “Мониторинг динамически меняющегося графа”, Труды ИСП РАН, 27:1 (2015), 69–96

Цитирование в формате AMSBIB
\RBibitem{BurKos15}
\by Игорь~Бурдонов, Александр~Косачев
\paper Мониторинг динамически меняющегося графа
\jour Труды ИСП РАН
\yr 2015
\vol 27
\issue 1
\pages 69--96
\mathnet{http://mi.mathnet.ru/tisp114}
\crossref{https://doi.org/10.15514/ISPRAS-2015-27(1)-5}
\elib{http://elibrary.ru/item.asp?id=23420342}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp114
  • http://mi.mathnet.ru/rus/tisp/v27/i1/p69

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. Игорь Бурдонов, Александр Косачев, “Параллельные вычисления на динамически меняющемся графе”, Труды ИСП РАН, 27:2 (2015), 189–220  mathnet  crossref  elib
    2. И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76  mathnet  crossref  elib
    3. I. B. Burdonov, A. S. Kossatchev, V. V. Kuliamin, A. N. Tomilin, V. Z. Shnitman, “Asynchronous distributed algorithms for static and dynamic directed rooted graphs”, Труды ИСП РАН, 30:1 (2018), 69–88  mathnet  crossref  elib
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:85
    Полный текст:29
    Литература:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020