Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов Научная публикация
Журнал |
Вестник Омского университета
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 |
Цитирование в БД:
Пока нет цитирований