|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Прикладная теория графов
Поиск кратчайших путей в оптимальных двумерных циркулянтах
Э. А. Монахова Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск, Россия
Аннотация:
Для семейства оптимальных двумерных циркулянтных сетей с аналитическим описанием получены две новые улучшенные версии алгоритма поиска кратчайших путей с константной оценкой сложности. Дано простое, основанное на геометрической модели циркулянтных графов, доказательство формул, используемых для алгоритма поиска кратчайших путей. Представлены алгоритмы парных обменов и даны их оценки для сетей на кристалле с топологией в виде рассмотренных графов. Новые версии алгоритма улучшают также предложенный ранее автором алгоритм поиска кратчайших путей для оптимальных обобщённых графов Петерсена с аналитическим описанием.
Ключевые слова:
двумерные циркулянтные графы, диаметр, кратчайшие пути, оптимальные обобщённые графы Петерсена, сети на кристалле.
Образец цитирования:
Э. А. Монахова, “Поиск кратчайших путей в оптимальных двумерных циркулянтах”, ПДМ, 2020, № 47, 87–100
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm696 https://www.mathnet.ru/rus/pdm/y2020/i1/p87
|
Статистика просмотров: |
Страница аннотации: | 184 | PDF полного текста: | 134 | Список литературы: | 16 |
|