Поиск кратчайших путей в оптимальных двумерных циркулянтах Э. А. Монахова
Material type:
ArticleOther title: A computation of the shortest paths in optimal two-dimensional circulant networks [Parallel title]Subject(s): двумерные циркулянтные графы | диаметры | кратчайшие пути | обобщенные графы Петерсена | сети на кристаллеGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 47. С. 87-100Abstract: Для семейства оптимальных двумерных циркулянтных сетей с аналитическим описанием получены две новые улучшенные версии алгоритма поиска кратчайших путей с константной оценкой сложности. Дано простое, основанное на геометрической модели циркулянтных графов, доказательство формул, используемых для алгоритма поиска кратчайших путей. Представлены алгоритмы парных обменов и даны их оценки для сетей на кристалле с топологией в виде рассмотренных графов. Новые версии алгоритма улучшают также предложенный ранее автором алгоритм поиска кратчайших путей для оптимальных обобщённых графов Петерсена с аналитическим описанием.
Библиогр.: 21 назв.
Для семейства оптимальных двумерных циркулянтных сетей с аналитическим описанием получены две новые улучшенные версии алгоритма поиска кратчайших путей с константной оценкой сложности. Дано простое, основанное на геометрической модели циркулянтных графов, доказательство формул, используемых для алгоритма поиска кратчайших путей. Представлены алгоритмы парных обменов и даны их оценки для сетей на кристалле с топологией в виде рассмотренных графов. Новые версии алгоритма улучшают также предложенный ранее автором алгоритм поиска кратчайших путей для оптимальных обобщённых графов Петерсена с аналитическим описанием.
There are no comments on this title.