Том 22, номер 6, 2015 г., Стр. 29–42

УДК 519.176
Монахова Э. А., Монахов О. Г.
Поиск рекордных циркулянтных графов с использованием параллельного генетического
алгоритма

Аннотация:
Рассматривается решение задачи построения больших неориентированных циркулянтных графов (сетей) с заданными степенью и диаметром. Разработан генетический алгоритм синтеза больших циркулянтных графов, и его параллельная версия реализована на суперкомпьютерных системах. Реализованный алгоритм нашёл 28 новых больших циркулянтных графов, порядки которых превосходят порядки самых больших известных циркулянтов из таблицы рекордных (Δ/D)-циркулянтов для степеней 12 ≤ Δ ≤ 16 и диаметров 4 ≤ D ≤ 10.
Табл. 2, библиогр. 29.

Ключевые слова: неориентированный циркулянтный граф, задача Δ/D, оптимизация сетей связи, генетический алгоритм.

DOI: 10.17377/daio.2015.22.509

Статья поступила 8 сентября 2015 г.
Исправленный вариант — 12 октября 2015 г.

Литература

[1] Корнеев В. В. О макроструктуре однородных вычислительных систем // Вычисл. системы. 1974. Вып. 60. С. 17–34.

[2] Монахова Э. А. Синтез оптимальных диофантовых структур // Вычисл. системы. 1979. Вып. 80. С. 18–35.

[3] Монахова Э. А. Об одном экстремальном семействе циркулянтных сетей // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 1. С. 77–84.

[4] Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикл. дискрет. математика. 2011. № 3. С. 92–115.

[5] Монахова Э. А. Новая достижимая нижняя оценка числа вершин в циркулянтных сетях размерности четыре // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 1. С. 37–44.

[6] Монахова Э. А. О построении многомерных циркулянтных графов диаметра два // Изв. Томск. политехн. ун-та. 2013. T. 323, № 2. C. 25–28.

[7] Bermond J. C., Comellas F., Hsu D. F. Distributed loop computer-networks: a survey // J. Parallel Distrib. Comput. 1995. Vol. 24, No. 1. P. 2–10.

[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. 1993. Vol. 23, No. 4. P. 257–260.

[10] Dougherty R., Faber V. The degree-diameter problem for several varieties of Cayley graphs. I: The Abelian case // SIAM J. DiscreteMath. 2004. Vol. 17, No. 3. P. 478–519.

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

[12] Elspas B., Turner J. Graphs with circulant adjacency matrices // J. Comb. Theory. 1970. Vol. 9, No. 3. P. 297–307.

[13] Feria-Purrón R., Ryan J., Pérez-Rosés H. Searching for large multi-loop networks // Electron. Notes Discrete Math. 2014. Vol. 46. P. 233–240.

[14] Feria-Purró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. 2003. Vol. 299, No. 1–3. P. 107–121.

[16] Lewis R. R. The degree-diameter problem for circulant graphs of degree 8 and 9 // Electron. J. Comb. 2014. Vol. 24, No. 4. P. 1–19.

[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., Siagiová J., Sirán J. Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups // Discrete Math. 2012. Vol. 312, No. 1. P. 94–99.

[19] Miller M., Sirán J. Moore graphs and beyond: A survey of the degree/diameter problem // Electron. J. Comb., Dyn. Surv. 2005. Vol. DS14. P. 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). Paris: INT, 2003. P. 410–415.

[21] Monakhova E. A. A survey on undirected circulant graphs // Discrete Math., Algorithms Appl. 2012. Vol. 4, No. 1. 1250002. P. 1–30.

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

[23] Muga II F. P. Maximal order of 3- and 5-regular circulant graphs // Matimyás Mat. 1999. Vol. 22, No. 3. P. 33–38.

[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. 2014. Vol. 2, No. 2. P. 166–190.

[25] Reeves C. R. Genetic algorithms for the operations researcher// INFORMS J. Comput. 1997. Vol. 9, No. 3. P. 231–250.

[26] The Degree/Diameter Problem // http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem.

[27] The Degree/Diameter Problem For Circulant Graphs //
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. 1974. Vol. 21, No. 3. P. 392–402.

[29] Wong C. K., Maddocks T. W. A generalized Pascal’s triangle // Fibonacci Quart. 1975. Vol. 13. P. 134–136.