Depth-First Search Algorithms for Finding a Generalized Moore Graph
Yoshiki Satotani, Norikazu Takahashi · 2018
Computer networks in data centers are often modeled by undirected regular graphs, and the average shortest path length (ASPL) of the graph is closely related to the data transmission latency. Therefore, finding an undirected regular graph with the minimum ASPL is an important problem for building a low latency network. An undirected regular graph is called a generalized Moore graph (GMG) when its ASPL is identical with the theoretical lower bound. Several methods have been proposed so far to find GMGs with given order and degree. However, they do not make a full use of the properties of GMGs. In this paper, we propose some efficient algorithms for finding a GMG and examine their effectiveness by experiments.