|
Записки научных семинаров ПОМИ, 2012, том 402, страницы 108–147
(Mi znsl5241)
|
|
|
|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Bases of schurian antisymmetric coherent configurations and isomorphism test for schurian tournaments
[Базы шуровых антисимметрических когерентных конфигураций и проверка изоморфизма шуровых турниров]
I. N. Ponomarenko St. Petersburg Department of Steklov Mathematical Institute RAS, St. Petersburg, Russia
Аннотация:
Хорошо известно, что для каждой группы перестановок $G$ нечетного порядка найдется множество точек, стабилизатор которого в $G$ тривиален, а если эта группа примитивна, то найдется и база размера не более 3. Эти результаты обобщаются на когерентную конфигурацию группы $G$ (в этом случае конфигурация шурова и антисимметрическая). Это позволяет построить алгоритм полиномиальной сложности для распознавания и проверки изоморфизма шуровых турниров (т.е. раскрашенных по дугам турниров, когерентные конфигурации которых шуровы). Библ. – 24 назв.
Ключевые слова:
когерентная конфигурация, линейная группа, сплетение, алгоритм Вейсфейлера–Лемана.
Поступило: 07.05.2012
Образец цитирования:
I. N. Ponomarenko, “Bases of schurian antisymmetric coherent configurations and isomorphism test for schurian tournaments”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 108–147; J. Math. Sci. (N. Y.), 192:3 (2013), 316–338
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5241 https://www.mathnet.ru/rus/znsl/v402/p108
|
Статистика просмотров: |
Страница аннотации: | 249 | PDF полного текста: | 67 | Список литературы: | 66 |
|