Тип публикации: статья из журнала
Год издания: 2020
Идентификатор DOI: 10.31772/2587-6066-2020-21-2-187-194
Ключевые слова: Cayley graph, permutation group, граф Кэли, группа подстановок
Аннотация: The purpose of this work is to create an effective routing algorithm on the Cayley graphs of permutation groups, superior in its characteristics to an algorithm using an automatic group structure. In the first section of the article we describe the auxiliary algorithm A-1 which allows numbering elements of a given permutation groupПоказать полностью. In the second section we present the algorithm A-2 for calculating the routing table on the Cayley graph and algorithm A-3 for determination the optimal route between two arbitrary vertices of the graph. Estimates of time and space complexity are also obtained for these algorithms. In the third section we describe the algorithm A-4 for calculation the minimal word of a group element. It is proved that the computational complexity of the algorithm will be proportional to the length of the input word. The fourth section presents the results of computer experiments for some groups of permutation groups, which compare the time for calculating the minimum words using algorithm A-4 and an algorithm based on the construction of an automatic group structure. It is shown that A-4 is much faster than its competitor. Целью настоящей работы является создание эффективного алгоритма маршрутизации на графах Кэли групп подстановок, превосходящего по своим характеристикам алгоритм, использующий автоматическую структуру группы. В первом разделе статьи описан вспомогательный алгоритм А-1, который позволяет нумеровать элементы заданной группы подстановок. Во втором разделе представлен алгоритм A-2 для вычисления таблицы маршрутизации на графе Кэли и алгоритм А-3, который позволяет определить оптимальный маршрут между двумя произвольными вершинами графа. Для данных алгоритмов также получены оценки временной и пространственной сложности. В третьем разделе описан алгоритм А-4, при помощи которого можно вычислить минимальное слово элемента группы. Доказано, что вычислительная сложность алгоритма будет пропорциональна длине входящего слова. В четвертом разделе приведены результаты компьютерных экспериментов для некоторых групп подстановок, в которых сравнивается время вычисления минимальных слов по алгоритму А-4 и алгоритму, основанному на построении автоматической групповой структуры. Показано, что А-4 значительно быстрее своего конкурента. (Русскоязычная версия представлена по адресу https://vestnik.sibsau.ru/articles/?id=677)
Журнал: Сибирский журнал науки и технологий
Выпуск журнала: Т. 21, № 2
Номера страниц: 187-194
ISSN журнала: 25876066
Место издания: Красноярск
Издатель: Сибирский государственный университет науки и технологий им. акад. М.Ф. Решетнева