RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2017 Volume 455, Pages 154–180 (Mi znsl6413)

This article is cited in 2 papers

Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time

I. Ponomarenkoa, A. Vasil'evbc

a St. Petersburg Department of the Steklov Mathematical Institute, St. Petersburg, Russia
b Sobolev Institute of Mathematics, Novosibirsk, Russia
c Novosibirsk State University, Novosibirsk, Russia

Abstract: A Cayley graph over a group $G$ is said to be central if its connection set is a normal subset of $G$. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order $n$, the set of all isomorphisms from the first graph onto the second can be found in time $\mathrm{poly}(n)$.

Key words and phrases: Cayley graph, almost simple group, polynomial-time algorithm.

UDC: 512.542+519.1

Received: 10.04.2017

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2018, 234:2, 219–236


© Steklov Math. Inst. of RAS, 2024