This article is cited in 2 papers

Searching for record circulant graphs using a parallel genetic algorithm

E. A. Monakhova, O. G. Monakhov

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 6 Lavrentiev Ave., 630090 Novosibirsk, Russia

Abstract: We consider the Degree/Diameter problem for circulants – the problem of constructing large undirected circulant graphs (networks) with given degree and diameter. We develop a genetic algorithm for synthesis of large circulant graphs and implement its parallel version by supercomputer systems. The algorithm has found 28 new large circulant graphs which orders are better than the largest of the current known circulants from the record $(\Delta/D)$-circulant graphs table for degrees $12\le\Delta\le16$ and diameters $4\le D\le10$. Tab. 2, bibliogr. 29.

Keywords: undirected circulant graph, Degree/Diameter problem, network design, genetic algorithm.

UDC: 519.176

Received: 08.09.2015
Revised: 12.10.2015

DOI: 10.17377/daio.2015.22.509

Bibliographic databases:

• 
•