Рассматривается задача оптимизации неориентированных циркулянтных сетей, состоящая в максимизации числа вершин при заданных степени и диаметре графа. Получена новая нижняя оценка достижимого числа вершин циркулянтных сетей размерности четыре при любых диаметрах. Построены новые бесконечные семейства циркулянтов, достигающих найденной оценки. Для графов найденных семейств получены различные аналитические описания.
Скачать электронную версию публикации
Загружен, раз: 97
- Title О построении циркулянтных сетей размерности четыре с максимальным числом вершин при любом диаметре
- Headline О построении циркулянтных сетей размерности четыре с максимальным числом вершин при любом диаметре
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(21)
- Date:
- DOI
Ключевые слова
неориентированные циркулянтные сети, диаметр, максимальный порядок графа, undirected circulant graphs, diameter, maximum order of a graphАвторы
Ссылки
Монахова Э. А. Новая достижимая нижняя оценка числа вершин в циркулянтных сетях размерности четыре // Дискретный анализ и исследование операций. 2013. Т. 20. №1. С.37-44.
Монахова Э.А. Оптимизация циркулянтных сетей связи размерности четыре // Дискретный анализ и исследование операций. 2008. Т. 15. №3. С. 58-64.
Dougherty R. and Faber V. The degree-diameter problem for several varieties of Cayley graphs, 1: the Abelian case // SIAM J. Discrete Math. 2004. V. 17. No.3. P. 478-519.
Monakhova E. A. Optimal triple loop networks with given transmission delay: topological design and routing // Inter. Network Optimization Conf. (IN0C'2003), Evry/Paris, France. 2003. P. 410-415.
Jia X.-D. and Su W. Triple loop networks with minimal transmission delay // Int. J. Found. Comp. Sci. 1997. V. 8. No. 3. P. 305-328.
Chen S. and Jia X.-D. Undirected loop networks // Networks. 1993. No. 23. P. 257-260.
Macbeth H., Siagiova J., and Siran J. Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups // Discrete Math. 2012. V.312. No. 1. P. 94-99.
Корнеев В. В. О макроструктуре однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 17-34.
Wong C.K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comp. Mach. 1974. No. 21. P. 392-402.
Воробьев В. А. Простейшие структуры однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1974. №60. С. 35-49.
Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discrete Appl. Math. 1997. No. 77. P. 281-305.
Muga F. P., Saldana R. P., and Yu W. E. S. Building graph-based symmetric cluster // NECTEC Techn. J. 2001. V. 11. No. 9. P. 195-199.
Narayanan L., Opatrny J., and Sotteau D. All-to-all optical routing in chordal rings of degree four // Algorithmica. 2001. V.31. No. 2. P. 155-178.
Comellas F., Mitjana M., and Peters J. G. Broadcasting in small-world communication networks // 9th Inter. Coll. on Structural Information and Communication Complexity (SIROCCO 9), 2002. Proc. Informatics. 2002. No. 13. P. 73-85.
Martinez C., Beivide R., and Gabidulin E. M. Perfect codes from Cayley graphs over Lipschitz integers // IEEE Trans. Inform. Theory. 2009. V.55. No. 8. P. 3552-3562.
Нестеренко Б. Б., Новотарский М. А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. №3. С. 132-138.
Bermond J.-C., Comellas F., and Hsu D. F. Distributed loop computer networks: a survey // J. Parallel Distributed Comput. 1995. V.24. P. 2-10.
Hwang F. K. A survey on multi-loop networks // Theor. Comp. Sci. 2003. No. 299. P. 107-121.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3(13). С. 92-115.
О построении циркулянтных сетей размерности четыре с максимальным числом вершин при любом диаметре | Прикладная дискретная математика. 2013. № 3(21).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 317