Preview

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

Расширенный поиск

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

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

Полный текст:

Аннотация

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

Об авторах

Игорь Бурдонов
Институт системного программирования РАН, г. Москва
Россия
Институт системного программирования РАН, 109004, Россия, г. Москва, ул. А. Солженицына, д. 25.


Александр Косачев
Институт системного программирования РАН, г. Москва
Россия
Институт системного программирования РАН, 109004, Россия, г. Москва, ул. А. Солженицына, д. 25.


Список литературы

1. Steven S. Skiena. The Algorithm Design Manual. Springer-Verlag, New York, 1997.

2. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай. Программирование, 2003 г., №5, с. 59-69.

3. И.Б. Бурдонов, А.С. Косачев, В.В. Кулямин. Неизбыточные алгоритмы обхода ориентированных графов. Недетерминированный случай. Программирование, 2004 г., №1, с. 2-17.

4. M.O. Rabin. Maze Threading Automata. An unpublished lecture presented at MIT and UC. Berkeley, 1967.

5. И.Б. Бурдонов. Обход неизвестного ориентированного графа конечным роботом. Программирование, 2004 г., № 4, с. 11-34.

6. И.Б. Бурдонов. Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом. Программирование, 2004 г., № 6, с. 6-29.

7. И. Бурдонов, А. Косачев, В. Кулямин. Параллельные вычисления на графе. Программирование, 2015, №1, с. 3-20.


Для цитирования:


Бурдонов И., Косачев А. Мониторинг динамически меняющегося графа. Труды Института системного программирования РАН. 2015;27(1):69-96. https://doi.org/10.15514/ISPRAS-2015-27(1)-5

For citation:


Burdonov I., Kosachev A. Monitoring of dynamically changed graph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(1):69-96. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(1)-5

Просмотров: 94


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


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