|
Zapiski Nauchnykh Seminarov POMI, 2017, Volume 455, Pages 154–180
(Mi znsl6413)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Received: 10.04.2017
Citation:
I. Ponomarenko, A. Vasil'ev, “Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time”, Problems in the theory of representations of algebras and groups. Part 31, Zap. Nauchn. Sem. POMI, 455, POMI, St. Petersburg, 2017, 154–180; J. Math. Sci. (N. Y.), 234:2 (2018), 219–236
Linking options:
https://www.mathnet.ru/eng/znsl6413 https://www.mathnet.ru/eng/znsl/v455/p154
|
Statistics & downloads: |
Abstract page: | 259 | Full-text PDF : | 63 | References: | 56 |
|