"Записки научных семинаров ПОМИ"
Том 455, стр. 154-180
Распознавание изоморфизма центральных графов Кэли над почти простыми группами за полиномиальное время
И. Пономаренко, А. Васильев
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
наб. р. Фонтанки 27, 191023, Санкт-Петербур, Россия
inp@pdmi.ras.ru
Sobolev Institute of Mathematics, Novosibirsk, Russia;
Novosibirsk State University, Novosibirsk, Russia
vasand@math.nsc.ru
- Аннотация:
Граф Кэли над группой $G$ называется центральным, если определяющее его подмножество является нормальным
в этой группе. Доказано, что для любой явно заданной почти простой группы $G$ порядка $n$ и любых двух
центральных графов Кэли над $G$ множество всех изоморфизмов первого графа на второй может быть найдено
за время $\mathrm{poly}(n)$.
Библ. -- 17 назв.
- Ключевые слова: граф Кэли, почти простая группа, алгоритм полиномиальной сложности
[Cayley graph, almost simple group, polynomial-time algorithm]
Полный текст(.pdf)