Volume 22, No 6, 2015, P. 29–42
UDC 519.176
E. A. Monakhova and O. G. Monakhov
Searching for record circulant graphs using a parallel genetic algorithm
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 (Δ/D)-circulant graphs table for degrees 12 ≤ Δ ≤ 16 and diameters 4 ≤ D ≤ 10.
Tab. 2, bibliogr. 29.
Keywords: undirected circulant graph, Degree/Diameter problem, network design, genetic algorithm.
DOI: 10.17377/daio.2015.22.509
Emilia A. Monakhova 1
Oleg G. Monakhov 1
1. Institute of Computational Mathematics and Mathematical Geophysics SB RAS,
6 Lavrentiev Ave., 630090 Novosibirsk, Russia
e-mail: emilia@rav.sscc.ru
Received 8 September 2015
Revised 12 October 2015
References
[1] V. V. Korneev, About macrostructure of homogeneous computing systems, in Vychislitel’nye sistemy (Computing Systems), Vol. 60, pp. 17–34, Izd. Inst. Mat., Novosibirsk, 1974.[2] E. A. Monakhova, Synthesis of optimal Diophantine structures, in Vychislitel’nye sistemy (Computing Systems), Vol. 80, pp. 18–35, Izd. Inst. Mat., Novosibirsk, 1979.
[3] E. A. Monakhova, On an extremal family of circulant networks, Diskretn. Anal. Issled. Oper., 18, No. 1, 77–84, 2011. Translated in J. Appl. Ind. Math., 5, No. 4, 595–600, 2011.
[4] E. A. Monakhova, Structural and communicative properties of circulant networks, Prikl. Diskretn. Mat., No. 3, 92–115, 2011.
[5] E. A. Monakhova, A new attainable lower bound on the number of nodes in quadruple circulant networks, Diskretn. Anal. Issled. Oper., 20, No. 1, 37–44, 2013.
[6] E. A. Monakhova, On synthesis of multidimensional circulant graphs of diameter two, Izv. TPU, 323, No. 2, 25–28, 2013.
[7] J. C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computer-networks: A survey, J. Parallel Distrib. Comput., 24, No. 1, 2–10, 1995.
[8] D. Bevan, G. Erskine, and R. Lewis, Large circulant graphs of fixed diameter and arbitrary degree, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1506.04962).
[9] S. Chen and X.-D. Jia, Undirected loop networks, Networks, 23, No. 4, 257–260, 1993.
[10] R. Dougherty and V. Faber, The degree-diameter problem for several varieties of Cayley graphs I: The Abelian case, SIAM J. Discrete Math., 17, No. 3, 478–519, 2004.
[11] B. Elspas, Topological constraints on interconnection-limited logic, Proc. 5th Annu. Symp. Switch. Circuit Theory Log. Des., Princeton, NJ, USA, Nov. 11–13, 1964, pp. 133–137, IEEE, New York, 1964.
[12] B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Comb. Theory, 9, No. 3, 297–307, 1970.
[13] R. Feria-Purrón, J. Ryan, and H. Pérez-Rosés, Searching for large multiloop networks, Electron. Notes Discrete Math., 46, 233–240, 2014.
[14] R. Feria-Purrón, H. Pérez-Rosés, and J. Ryan, Searching for large circulant graphs, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1503.07357).
[15] F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci., 299, No. 1–3, 107–121, 2003.
[16] R. R. Lewis, The degree-diameter problem for circulant graphs of degree 8 and 9, Electron. J. Comb., 24, No. 4, P4.50, 1–19, 2014.
[17] R. R. Lewis, Improved upper bounds for the order of some classes of Abelian Cayley and circulant graphs of diameter two, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1506.02844).
[18] H. Macbeth, J. Siagiová and J. Sirán, Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups, Discrete Math., 312, No. 1, 94–99, 2012.
[19] M. Miller and J. Sirán, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Comb., Dyn. Surv., DS14, 1–61, 2005.
[20] E. A. Monakhova, Optimal triple loop networks with given transmission delay: Topological design and routing, Proc. Int. Network Optim. Conf., Évry/Paris, France, Oct. 27–29, 2003, pp. 410–415, INT, Paris, 2003.
[21] E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl., 4, No. 1, 1250002, 1–30, 2012.
[22] E. A. Monakhova, O. G. Monakhov, and E. V. Mukhoed, Genetic construction of optimal circulant network designs, in Evolutionary Image Analysis, Signal Processing and Telecommunications (Proc. 1st Eur. Workshops EvoIASP’99 EuroEcTel’99, Göteborg, Sweden, May 26–27, 1999), pp. 215–223, Springer, Heidelberg, 1999 (Lect. Notes Comput. Sci., Vol. 1596).
[23] F. P. Muga II, Maximal order of 3- and 5-regular circulant graphs,Matimyás Mat., 22, No. 3, 33–38, 1999.
[24] H. Pérez-Rosés, Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey, Electron. J. Graph Theory Appl., 2, No. 2, 166–190, 2014.
[25] C. R. Reeves, Genetic algorithms for the operations researcher, INFORMS J. Comput., 9, No. 3, 231–250, 1997.
[26] The Degree/Diameter Problem, in Combinatorics Wiki. Available at
http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem. Accessed Nov. 2, 2015.
[27] The Degree Diameter Problem for Circulant Graphs. in Combinatorics Wiki. Available at http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs. Accessed Nov. 2, 2015.
[28] C. K. Wong and Don Coppersmith, A combinatorial problem related to multimodule memory organizations, J. Assoc. Comput. Mach., 21, No. 3, 392–402, 1974.
[29] C. K. Wong and T. W. Maddocks, A generalized Pascal’s triangle, Fibonacci Q., 13, 134–136, 1975.
