Sciact
  • EN
  • RU

Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов Научная публикация

Журнал Вестник Омского университета
ISSN: 1812-3996
Вых. Данные Год: 2022, Том: 27, Номер: 2, Страницы: 13-16 Страниц : 4 DOI: 10.24147/1812-3996.2022.27(2).13-16
Ключевые слова Генерическая сложность, изоморфизм графов, двудольный граф
Авторы Рыбалов А.Н. 1
Организации
1 Институт математики им. С. Л. Соболева СО РАН, Омский филиал, г. Омск, Россия

Информация о финансировании (1)

1 Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». FWNF-2022-0003

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