ГлавнаяАрхивСерии семейств циркулянтных графов степени шесть

Серии семейств циркулянтных графов степени шесть | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/6

Предложен подход к построению и оптимизации графов серий аналитически описываемых циркулянтных графов степени шесть с общими топологическими свойствами. Представлены три серии семейств неориентированных циркулянтов вида C(N(d,p);1,s2(d,p),s3(d,p)) произвольного диаметра d > 1 с переменным параметром p(d), 1 ≤ p(d)≤ d. Порядки N каждого графа в семействах определяются кубическим полиномом от диаметра, а образующие s2 - полиномами от диаметра различных порядков. Доказано, что найденные серии семейств включают экстремальные циркулянтные графы степени 6 с самыми большими известными порядками для всех диаметров. Посредством задания функций p(d) построены новые бесконечные семейства циркулянтных графов, включая решения, близкие к экстремальным графам.
  • Title Серии семейств циркулянтных графов степени шесть
  • Headline Серии семейств циркулянтных графов степени шесть
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 54
  • Date:
  • DOI 10.17223/20710410/54/6
Ключевые слова
граф Кэли абелевой группы, проблема d/k графов, семейства циркулянтных графов степени 6, трёхмерные кольцевые циркулянтные графы, экстремальные циркулянтные графы
Авторы
Ссылки
Monakhova E. A. A survey on undirected circulant graphs. Discr. Math. Algorithms Appl., 2012, vol.4, no. 1, 1250002, 30 p.
Bermond J.-C., Cornelias F., and Hsu D.F. Distributed loop computer networks: a survey. J. Parallel Distrib. Comput., 1995, vol. 24, pp. 2-10.
Feria-Puron R., Perez-Roses H., and Ryan J. Searching for Large Circulant Graphs. arXiv:1503.07357v1 [math.CO], Aug. 11, 2018, 31 p.
Hwang F. K. A survey on multi-loop networks. Theor. Comput. Sci., 2003, vol. 299, pp.107-121.
Chen S. and Jia X.-D. Undirected loop networks. Networks, 1993, no. 23(4), pp. 257-260.
Stojmenovie I. Multiplicative circulant networks. Topological properties and communication algorithms. Discr. Appl. Math., 1997, no. 77, pp. 281-305.
Thomson A. and Zhou S. Gossiping and routing in undirected triple-loop networks. Networks, 2010, no. 55(4), pp. 341-349.
Wong C. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations. J. Assoc. Comput. Mach., 1974, no. 21(3), pp. 392-402.
Monakhova E. Optimal triple loop networks with given transmission delay: Topological design and routing. Proc. INOC’2003, Evry/Paris, France, 2003, pp. 410-415.
Lewis R. R. The degree-diameter problem for circulant graphs of degree 8 and 9. Electron. J. Combin., 2014, no. 21(4), article no. P4.50.
Lewis R. R. The degree-diameter problem for circulant graphs of degrees 10 and 11. Discrete Math., 2018, no. 341, pp. 2553-2566.
Dalfo C., Fiol M. A., Lopez N., and Ryan J. An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs. Discr. Math., 2020, vol. 343, no. 10.
Miller M. and Siran J. Moore graphs and beyond: A survey of the degree/diameter problem. Electron. J. Combin., Dyn. Surv., 2005, no. DS14, 61 p.
Perez-Roses H. Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey. Electron. J. Graph Theory Appl., 2014, no. 2(2), pp. 166-190.
The Degree/Diameter Problem For Circulant Graphs. http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs.
Monakhova E. A., Romanov A. Yu., and Lezhnev E. V. Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip. IEEE Access, 2020, no. 8, pp. 215010-215019.
Romanov A., Amerikanov A., and Lezhnev E. Analysis of approaches for synthesis of networks-on-chip by using circulant topologies. J. Physics. Conf. Series, 2018, vol. 1050, no. 1, pp. 1-12.
Monakhova E. A., Monakhov O. G., Romanov A. Yu., and Lezhnev E. V. Analytical routing algorithm for networks-on-chip with the three-dimensional circulant topology. Proc. MWENT 2020, Moscow, Russia, March 11-13, 2020, pp. 1-6.
Romanov A. Yu. and Starykh V. A. Routing in triple loop circulants: A case of networks-on-chip. Heliyon, 2020, no.6(7), pp. 1-7.
Ansari A. Q., Ansari M. R., and Khan M. A. Modified quadrant-based routing alglrithm for 3D torus network-on-chip architecture. Perspect. Sci., 2016, vol. 8, pp. 718-721.
Joseph J.M., Blochwitz C., Garcia-Ortiz A., and Pionteck T. Area and power savings via asymmetric organization of buffers in 3D-NoCs for heterogeneous 3D-SoCs. Microprocess. Microsyst., 2017, vol. 48, pp. 36-47.
Yebra J. L. A., Fiol M. A., Morillo P., and Alegre I. The diameter of undirected graphs associated to plane tessellations. Ars Combinatoria, 1985, no. 20B, pp. 159-171.
Martinez C., Stafford E., Beivide R., and Gabidulin E. M. Modeling hexagonal constellations with Eisenstein - Jacobi graphs. Problems Inform. Transmission, 2008, no. 44(1), pp. 1-11.
Barriere L., Fabrega J., Simo E., and Zaragoza M. Fault-tolerant routings in chordal ring networks. Networks, 2000, no. 36(3), pp. 180-190.
Liestman A. L., Opatrny J., and Zaragoza M. Network properties of double and triple fixed-step graphs. Int. J. Found. Comp. Sci., 1998, no. 9(1), pp. 57-76.
Jha P. K. A family of efficient six-regular circulants representable as a Kronecker product. Discr. Appl. Math., 2016, no. 203, pp. 72-84.
Parhami B. A class of odd-radix chordal ring networks. CS’J J. Comput. Sci. Eng., 2006, vol. 4, no. 2-4, pp. 1-9.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley Graphs, 1: The Abelian case. SIAM J. Discr. Math., 2004, no. 17(3), pp. 478-519.
Monakhova E. A. Parametricheskoe zadanie serii semeystv analiticheski opisyvaemykh tsirkulyantnykh setey stepeni shest’ [A set of families of analytically described triple loop networks defined by a parameter]. Prikladnaya Diskretnaya Matematika, 2020, no. 49, pp. 108-119. (in Russian)
Monakhova E. A. and Monakhov O. G. Dinamicheskij algoritm parnoj marshrutizacii dlya analiticheski zadavaemyh semeystv cirkulyantnyh setey stepeni shest’ [A dynamic algorithm of two-terminal routing for analytically described families of circulant networks of degree six]. Proc. XIX Inter. Conf. “Problems of Information in Education, Management, Economics and Technology”, Penza, Russia, 2019, pp. 30-37. (in Russian)
Серии семейств циркулянтных графов степени шесть | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/6
Серии семейств циркулянтных графов степени шесть | Прикладная дискретная математика. 2021. № 54. DOI: 10.17223/20710410/54/6