Замыкания групп подстановок и проблема изоморфизма Научная публикация
| Журнал |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Вых. Данные | Год: 2023, Том: 28, Номер: 5, Страницы: 6-10 Страниц : 5 DOI: 10.24147/1812-3996.2023.5.6-10 | ||
| Ключевые слова | группа подстановок, орбита, -замыкание группы подстановок, конечный граф, многомерная когерентная конфигурация, проблема изоморфизма | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0002 |
Реферат:
Проблема изоморфизма графов состоит в нахождении наиболее эффективного алгоритма проверки изоморфизма двух данных конечных графов. Несмотря на значительные усилия многих математиков в последние 50 лет, время работы лучших из предложенных алгоритмов остается по существу экспоненциальным. Прорывом в этой области стал результат Л. Бабаи, предлагающий квазиполиномиальный алгоритм проверки изоморфизма графов. Основные составляющие этого алгоритма: теория конечных групп подстановок, многомерные когерентные конфигурации и алгоритмы Бабаи-Лакса и Вейс-фейлера-Лемана. В работе идет речь о замыканиях групп подстановок и связи проблемы нахождения таких замыканий и проблемы изоморфизма графов
Библиографическая ссылка:
Васильев А.В.
Замыкания групп подстановок и проблема изоморфизма
Вестник Омского университета. 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 РИНЦ
Даты:
| Поступила в редакцию: | 20 окт. 2023 г. |
| Опубликована в печати: | 10 дек. 2023 г. |
| Опубликована online: | 19 дек. 2023 г. |
Идентификаторы БД:
| РИНЦ: | 57174747 |
Цитирование в БД:
Пока нет цитирований