Том 18, номер 1, 2011 г., Стр. 77-84
УДК 519.87
Монахова Э. А.
Об одном экстремальном семействе циркулянтных сетей
Аннотация:
Рассматривается задача оптимизации циркулянтных сетей, состоящая в максимизации числа вершин при заданных степени и диаметре графа. Для графов наилучшего известного экстремального семейства циркулянтных сетей улучшена оценка диаметра, что вместе с результатами, полученными ранее для мультипликативных циркулянтных сетей, позволило улучшить нижние оценки достижимого числа вершин циркулянтных сетей всех размерностей$k\ge4$ .
Библиогр. 12.
Ключевые слова: циркулянтная сеть, диаметр, максимальный порядок графа.
Монахова Эмилия Анатольевна 1
1. Институт вычислительных технологий СО РАН,
пр. Aкад. Лаврентьева, 6, 630090 Новосибирск, Россия
е-mail: emilia@rav.sscc.ru
Статья поступила 29 июля 2010 г.
Исправленный вариант — 11 ноября 2010 г.
Литература
[1] Монахов О. Г., Монахова Э. А. Параллельные системы с распределенной памятью: структуры и организация взаимодействий. — Новосибирск: Изд-во СО РАН, 2000. — 242 с.
[2] Монахова Э. А. Оптимизация циркулянтных сетей связи размерности четыре // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 3. — С. 58–64.
[3] Монахова Э. А. Мультипликативные циркулянтные сети // Дискрет. анализ и исслед. операций. — 2010. —Т. 17, № 5. — C. 56–66.
[4] Bermond J.-C., Comellas F., Hsu D. F. Distributed loop computer networks: a survey // J. Parallel Distributed Comput. — 1995. — Vol. 24. — P. 2–10.
[5] Chen S., Jia X.-D. Undirected loop networks // Networks. — 1993. — Vol. 23. — P. 257–260.
[6] Hwang F. K. A survey on multi-loop networks // Theoret. Comput. Sci. — 2003.– Vol. 299. — P. 107–121.
[7] Monakhov O. G., Monakhova E. A. Computer discovery of analytical descriptions of families of circulant networks // Proc. 6th Intern. Conf. Soft Computing and Measurements SCM’2003 (St.-Petersburg, Russia, 2003). Vol. 1. — St. Petersburg: LETI, 2003. — P. 345–348.
[8] Monakhova E. Optimal triple loop networks with given transmission delay: topological design and routing // Proc. Intern. Network Optimization Conf. (INOC’2003) ( Evry/Paris, France, 2003). — Paris: INT, 2003. — P. 410–415.
[9] Muga F. P. Undirected circulant graphs // Proc. Intern. Symp. Parallel Architectures, Algorithms, and Networks. — Los Alamitos: IEEE Press, 1994. — P. 113–118.
[10] Parhami B. A class of odd-radix chordal ring networks // The CS’J J. Comput. Sci. Engineering. — 2006. — Vol. 4, N 2–4. — P. 1–9.
[11] Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms // Discrete Appl. Math. — 1997. — Vol. 77. — P. 281–305.
[12] Wong C. K., Don Coppersmith. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. — 1974. — Vol. 21. — P. 392–402.
