Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов Научная публикация
| Журнал |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Вых. Данные | Год: 2022, Том: 27, Номер: 2, Страницы: 13-16 Страниц : 4 DOI: 10.24147/1812-3996.2022.27(2).13-16 | ||
| Ключевые слова | Генерическая сложность, изоморфизм графов, двудольный граф | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
Проблема изоморфизма для двудольных графов так же вычислительно
трудна, как и известная проблема изоморфизма произвольных конечных графов, для
которой неизвестно полиномиальных алгоритмов. Предлагается полиномиальный генерический алгоритм для проблемы изоморфизма двудольных графов, который дает
правильный ответ на множестве почти всех входов, а на редких оставшихся входах
дает неопределенный ответ.
Библиографическая ссылка:
Рыбалов А.Н.
Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов
Вестник Омского университета. 2022. Т.27. №2. С.13-16. DOI: 10.24147/1812-3996.2022.27(2).13-16 РИНЦ OpenAlex
Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов
Вестник Омского университета. 2022. Т.27. №2. С.13-16. DOI: 10.24147/1812-3996.2022.27(2).13-16 РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 29 апр. 2022 г. |
| Принята к публикации: | 4 июл. 2022 г. |
| Опубликована online: | 8 сент. 2022 г. |
| Опубликована в печати: | 9 сент. 2022 г. |
Идентификаторы БД:
| РИНЦ: | 49492553 |
| OpenAlex: | W4403541721 |
Цитирование в БД:
Пока нет цитирований