Об одном алгоритме маршрутизации на графах Кэли, порожденных группами подстановок
Автор: Кузнецов А.А., Кишкан В.В.
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 2 т.21, 2020 года.
Бесплатный доступ
Целью настоящей работы является создание эффективного алгоритма маршрутизации на графах Кэли групп подстановок, превосходящего по своим характеристикам алгоритм, использующий автоматическую структуру группы. В первом разделе статьи описан вспомогательный алгоритм А-1, который позволяет нумеровать элементы заданной группы подстановок. Во втором разделе представлен алгоритм A-2 для вычисления таблицы маршрутизации на графе Кэли и алгоритм А-3, который позволяет определить оптимальный маршрут между двумя произвольными вершинами графа. Для данных алгоритмов также получены оценки временной и пространственной сложности. В третьем разделе описан алгоритм А-4, при помощи которого можно вычислить минимальное слово элемента группы. Доказано, что вычислительная сложность алгоритма будет пропорциональна длине входящего слова. В четвертом разделе приведены результаты компьютерных экспериментов для некоторых групп подстановок, в которых сравнивается время вычисления минимальных слов по алгоритму А-4 и алгоритму, основанному на построении автоматической групповой структуры. Показано, что А-4 значительно быстрее своего конкурента. (Русскоязычная версия представлена по адресу https://vestnik.sibsau.ru/articles/?id=677)
Граф кэли, группа подстановок
Короткий адрес: https://sciup.org/148321964
IDR: 148321964 | DOI: 10.31772/2587-6066-2020-21-2-187-194
Список литературы Об одном алгоритме маршрутизации на графах Кэли, порожденных группами подстановок
- Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications (Editors: Hahnand Sabidussi). Dordrecht: Kluwer Academic Publishers. 1997, P. 167-226.
- Loz E. New record graphs in the degree-diameter problem. Australasian Journal of Combinatorics. 2008, Vol. 41, P. 63-80.
- Even S., Goldreich O. The Minimum Length Generator Sequence is NP-Hard. Journal of Algorithms. 1981, Vol. 2, P. 311-313.
- Holt D., Eick B., O'Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005, 514 p.
- Schibell S., Stafford R. Processor interconnection networks and Cayley graphs. Discrete Applied Mathematics. 1992, Vol. 40, P. 337-357.
- Stamoulis G., Tsitsiklis J. Effcient routing Scheme for Multiple Broadcasts in Hypercubes. IEEE Trans. on Parallel and Distributed Systems. 1993, Vol. 4(7), P. 725-739.
- Stamoulis G., Tsitsiklis J. The Effciency of Greedy Routing in Hypercubes and Butteries. IEEE Transaction on Communication. 1994, Vol. 42(11), P. 3051-3061.
- Kiasari A., Sarbazi-Azad H. Analytic performance comparison of hypercubes and star graphs with implementation constraints. Journal of Computer and System Sciences. 2008, No. 6, P. 1000-1012.
- Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. Proceedings of the International Conference on Parallel Processing. 1986, P. 216-223.
- Tang K., Arden B. Vertex-transitivity and routing for Cayley graphs in GCR representations. Proceedings of ACM Symposium on Applied Computing SAC. 1992, P. 1180-1187.
- Wang L., Tang K. Topology-Based Routing for Xmesh in Wireless Sensor Networks. Lecture Notes in Electrical Engineering. 2009, Vol. 44, P. 229-239.
- Ryu J., Noel E., and Tang K. Fault-tolerant Routing on Borel Cayley Graph. IEEE ICC Next Generation Networking Symposium. 2012, P. 2872-2877.
- Shin J., Sirer E., Weatherspoon H., Kirovski D. On the feasibility of completely wireless datacenters. EEE/ACM Transaction On Networking. 2013, Vol. 21(5), P. 1666-1679.
- Epstein D., Paterson M., Cannon J., Holt D., Levy S. and Thurston W. Word Processing in Groups. Boston: Jones and Barlett Publishers, 1992, 330 p.
- Camelo M., Papadimitriou D., Fabrega L., Vila P. Efficient Routing in Data Center with Underlying Cayley Graph. Proceedings o/ the 5th Workshop on Complex Networks CompleNet. 2014, P. 189-197.
- Knuth D. The Art o/ Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Boston: Addison-Wesley Professional, 2011, 912 p.
- Sims C. Computational methods in the study of permutation groups, Computational problems in abstract algebra (Pergamon Press, Ox/ord). 1970, P.169-183.
- Seress A. Permutation Group Algorithms. Cambridge: Cambridge University Press, 2003, 274 p.
- Skiena S. The Algorithm Design Manual. London: Springer Science+Business Media, 2008, 730 p.
