A Method for Automatic Search for Families of Optimal Chordal Ring Networks

Arden and Lee proposed a class of chordal ring networks of degree three as communicationnetworks for multicomputer systems, derived a formula for the diameter, and produced analgorithm for finding the shortest paths for them. In this paper, it is shown that the formula forthe diameter and the routing algorithm presented by them are inaccurate. We have obtained alarge dataset containing parameters for describing optimal diameter chord rings for all thenumbers of nodes up to 60 000 and found the exact lower bound for the diameter of chordal ringnetworks. A new method is proposed and the algorithms for automatic search for analyticaldescriptions of families of optimal chordal rings are realized based on an analysis of the database.Using the latter, analytical descriptions of over 500 new families of optimal chordal ring networksfor many values of the number of nodes are found (only six families have been known until now inthe literature).