Geodesic
Searching for record circulant graphs using a~parallel genetic algorithm
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 29-42.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2015_22_6_a1,
     author = {E. A. Monakhova and O. G. Monakhov},
     title = {Searching for record circulant graphs using a~parallel genetic algorithm},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {29--42},
     publisher = {mathdoc},
     volume = {22},
     number = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_6_a1/}
}
TY  - JOUR
AU  - E. A. Monakhova
AU  - O. G. Monakhov
TI  - Searching for record circulant graphs using a~parallel genetic algorithm
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 29
EP  - 42
VL  - 22
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_6_a1/
LA  - ru
ID  - DA_2015_22_6_a1
ER  - 
%0 Journal Article
%A E. A. Monakhova
%A O. G. Monakhov
%T Searching for record circulant graphs using a~parallel genetic algorithm
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 29-42
%V 22
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_6_a1/
%G ru
%F DA_2015_22_6_a1
E. A. Monakhova; O. G. Monakhov. Searching for record circulant graphs using a~parallel genetic algorithm. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 29-42. http://geodesic.mathdoc.fr/item/DA_2015_22_6_a1/

[1] V. V. Korneev, “About macrostructure of homogeneous computing systems”, Computing Systems, 60, Izd. Inst. Mat., Novosibirsk, 1974, 17–34 | Zbl

[2] E. A. Monakhova, “Synthesis of optimal Diophantine structures”, Computing Systems, 80, Izd. Inst. Mat., Novosibirsk, 1979, 18–35 | MR | Zbl

[3] E. A. Monakhova, “On an extremal family of circulant networks”, J. Appl. Ind. Math., 5:4 (2011), 595–600 | DOI | MR | Zbl

[4] E. A. Monakhova, “Structural and communicative properties of circulant networks”, Prikl. Diskretn. Mat., 2011, no. 3, 92–115

[5] E. A. Monakhova, “A new attainable lower bound on the number of nodes in quadruple circulant networks”, Diskretn. Anal. Issled. Oper., 20:1 (2013), 37–44 | MR | Zbl

[6] E. A. Monakhova, “On synthesis of multidimensional circulant graphs of diameter two”, Izv. TPU, 323:2 (2013), 25–28

[7] Bermond J. C., Comellas F., Hsu D. F., “Distributed loop computer-net-works: a survey”, J. Parallel Distrib. Comput., 24:1 (1995), 2–10 | DOI

[8] Bevan D., Erskine G., Lewis R., Large circulant graphs of fixed diameter and arbitrary degree, arXiv: 1506.04962v1[math.CO]

[9] Chen S., Jia X.-D., “Undirected loop networks”, Networks, 23:4 (1993), 257–260 | DOI | MR | Zbl

[10] Dougherty R., Faber V., “The degree-diameter problem for several varieties of Cayley graphs. I: The Abelian case”, SIAM J. Discrete Math., 17:3 (2004), 478–519 | DOI | MR | Zbl

[11] Elspas B., “Topological constraints on interconnection-limited logic” (Princeton, NJ, USA, Nov. 11–13, 1964), Proc. 5th Annu. Symp. Switching Circuit Theory and Logic Design, 1964, 133–147, IEEE, New York

[12] Elspas B., Turner J., “Graphs with circulant adjacency matrices”, J. Comb. Theory, 9:3 (1970), 297–307 | DOI | MR | Zbl

[13] Feria-Purón R., Ryan J., Pérez-Rosés H., “Searching for large multi-loop networks”, Electron. Notes Discrete Math., 46 (2014), 233–240 | DOI

[14] Feria-Purón R., Pérez-Rosés H., Ryan J., Searching for large circulant graphs, arXiv: 1503.07357v1[math.CO]

[15] Hwang F. K., “A survey on multi-loop networks”, Theor. Comput. Sci., 299:1–3 (2003), 107–121 | DOI | MR | Zbl

[16] Lewis R. R., “The degree-diameter problem for circulant graphs of degree 8 and 9”, Electron. J. Comb., 24:4 (2014), 1–19 | MR

[17] Lewis R. R., Improved upper bounds for the order of some classes of Abelian Cayley and circulant graphs of diameter two, arXiv: 1506.02844v1[math.CO]

[18] Macbeth H., Šiagiová J., Širáň J., “Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups”, Discrete Math., 312:1 (2012), 94–99 | DOI | MR | Zbl

[19] Miller M., Širáň J., “Moore graphs and beyond: A survey of the degree/diameter problem”, Electron. J. Comb., Dyn. Surv., DS14 (2005), 1–61

[20] Monakhova E., “Optimal triple loop networks with given transmission delay: Topological design and routing”, Proc. Int. Network Optimization Conf., INOC'2003 (Èvry/Paris, France, Oct. 27–29, 2003), INT, Paris, 2003, 410–415

[21] Monakhova E. A., “A survey on undirected circulant graphs”, Discrete Math., Algorithms Appl., 4:1 (2012), 1250002, 30 pp. | DOI | MR | Zbl

[22] Monakhova E. A., Monakhov O. G., Mukhoed E. V., “Genetic construction of optimal circulant network designs” (Göteborg, Sweden, May 26–27, 1999), Proc. 1st Eur. Workshops EvoIASP'99 and EuroEcTel'99, Lect. Notes Comput. Sci., 1596, Springer-Verl., Heidelberg, 1999, 215–223

[23] Muga II F. P., “Maximal order of 3- and 5-regular circulant graphs”, Matimyás Mat., 22:3 (1999), 33–38 | MR | Zbl

[24] Pérez-Rosés H., “Algebraic and computer-based methods in the undirected degree/diameter problem – A brief survey”, Electron. J. Graph Theory Appl., 2:2 (2014), 166–190 | DOI | MR | Zbl

[25] Reeves C. R., “Genetic algorithms for the operations researcher”, INFORMS J. Comput., 9:3 (1997), 231–250 | DOI | Zbl

[26] The Degree/Diameter Problem, Combinatorics Wiki. Available at: , Accessed Nov. 2, 2015 http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem

[27] The Degree/Diameter Problem For Circulant Graphs, Combinatorics Wiki. Available at , Accessed Nov. 2, 2015 http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs

[28] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21:3 (1974), 392–402 | DOI | MR | Zbl

[29] Wong C. K., Maddocks T. W., “A generalized Pascal's triangle”, Fibonacci Quart., 13 (1975), 134–136 | MR | Zbl