A faster algorithm to search for generalized Moore graphs
A faster algorithm to search for generalized Moore graphs
复制标题
搜索广义摩尔图的更快算法
DOI：
10.1109/tencon55691.2022.9977538
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tsuyoshi Migita and Norikazu Takahashi
中科院分区：
文献类型：
--
作者：
Taku Hirayama;Tsuyoshi Migita and Norikazu Takahashi
一个平均最短路径长度(ASPL)等于某个下界的无向正则图称为广义Moore图(GMG)。数据中心的计算机网络通常被建模为无向正则图，而网络中的数据传输延迟与相应图的ASPL密切相关。因此，寻找具有指定阶数和度数的GMG是设计低延迟网络的一个重要问题。虽然这个问题在图论中已经研究了很多年，但GMG的存在条件仍然不清楚。此外，目前还没有快速的算法来搜索GMG。本文对现有的GMG深度优先搜索算法进行了改进，并通过实验验证了算法的有效性。
An undirected regular graph whose average shortest path length (ASPL) is equal to a certain lower bound is called a generalized Moore graph (GMG). Computer networks in data centers are often modeled as undirected regular graphs, and data transmission latency in a network is closely related to the ASPL of the corresponding graph. Therefore, finding a GMG with prescribed order and degree is an important problem for designing low-latency networks. Although this problem has been studied in graph theory for many years, the conditions for existence of a GMG is still not clear. In addition, there is no fast algorithm to search for GMGs. In this paper, we propose a modified version of an existing depth-first search algorithm for GMGs, and verify its effectiveness through experiments.