Using evolutionary algorithm for generation of dense families of circulant networks

In this paper we consider the combinatorial optimization problem of the search for dense families of circulant networks with a good ratio between the order and diameter for a given degree. In particular, we distinguish the optimal families having the minimum possible diameter for a given degree and order of a graph. This work describes a new way of generation of analytical parametric descriptions of dense families of circulant networks using evolutionary algorithms. We present the families of circulants of degree 4 and 6 obtained by means of evolutionary algorithms. Some of these families of degree 6 improve previously known results.

I. INTRODUCTION

Circulant networks are widely studied in computer science and discrete mathematics [2], [4], [5], [13]. They have a vast number of applications in computer systems, telecommunication networks, and VLSI design. These graphs have been realized as interconnection networks for some massively parallel processing systems. It has been shown in [11] that circulant graphs are better than hypercube topology with respect to the diameter and average distance. Such structures require a substantially smaller number of interprocessor exchanges than hypercubes for the realization of collective and individual change schemes such as gossiping, broadcasting and routing.