A Faster Algorithm to Search for Generalized Moore Graphs

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.