Об одном алгоритме маршрутизации на графах Кэли, порожденных группами подстановок

Бесплатный доступ

Целью настоящей работы является создание эффективного алгоритма маршрутизации на графах Кэли групп подстановок, превосходящего по своим характеристикам алгоритм, использующий автоматическую структуру группы. В первом разделе статьи описан вспомогательный алгоритм А-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.
Еще
Статья научная