Замыкания групп подстановок и проблема изоморфизма Full article
| Journal |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Output data | Year: 2023, Volume: 28, Number: 5, Pages: 6-10 Pages count : 5 DOI: 10.24147/1812-3996.2023.5.6-10 | ||
| Tags | группа подстановок, орбита, -замыкание группы подстановок, конечный граф, многомерная когерентная конфигурация, проблема изоморфизма | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0002 |
Abstract:
Проблема изоморфизма графов состоит в нахождении наиболее эффективного алгоритма проверки изоморфизма двух данных конечных графов. Несмотря на значительные усилия многих математиков в последние 50 лет, время работы лучших из предложенных алгоритмов остается по существу экспоненциальным. Прорывом в этой области стал результат Л. Бабаи, предлагающий квазиполиномиальный алгоритм проверки изоморфизма графов. Основные составляющие этого алгоритма: теория конечных групп подстановок, многомерные когерентные конфигурации и алгоритмы Бабаи-Лакса и Вейс-фейлера-Лемана. В работе идет речь о замыканиях групп подстановок и связи проблемы нахождения таких замыканий и проблемы изоморфизма графов
Cite:
Васильев А.В.
Замыкания групп подстановок и проблема изоморфизма
Вестник Омского университета. 2023. Т.28. №5. С.6-10. DOI: 10.24147/1812-3996.2023.5.6-10 РИНЦ
Замыкания групп подстановок и проблема изоморфизма
Вестник Омского университета. 2023. Т.28. №5. С.6-10. DOI: 10.24147/1812-3996.2023.5.6-10 РИНЦ
Dates:
| Submitted: | Oct 20, 2023 |
| Published print: | Dec 10, 2023 |
| Published online: | Dec 19, 2023 |
Identifiers:
| Elibrary: | 57174747 |
Citing:
Пока нет цитирований