A New Approach for Automatic Search for Families of Optimal Undirected Double-Loop Networks

Based on the analysis of a large dataset for optimal undirected double-loop networks, we studied the problem of finding families of optimal double-loop graphs with the minimal possible diameter. Optimal double-loop networks are of practical interest as graph models for reliable, low-delay communication in computer systems and networks-on-chip, due to their advantageous networking properties. A large dataset of optimal double-loop networks with up to 50000 nodes and all the optimal generators for given graph orders were built. We automated the process of searching for analytical (described by polynomials in diameter) descriptions of the families of optimal double-loop networks. After applying the integration of differential evolution methods, exhaustive local search, and a new search algorithm (based on the division of graph description polynomials) to the analysis of the generated dataset, we found a large amount of new (distinct from all previously known) families of optimal double-loop networks with generators of linear or quadratic types. Based on the analysis of the constructed dataset, a method for accelerated search for finding descriptions of optimal double-loop networks using second-order surface approximation was proposed. Our new approach can be used for the analysis of datasets of other promising classes of graphs and networks.