Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов Full article
| Journal |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Output data | Year: 2022, Volume: 27, Number: 2, Pages: 13-16 Pages count : 4 DOI: 10.24147/1812-3996.2022.27(2).13-16 | ||
| Tags | Генерическая сложность, изоморфизм графов, двудольный граф | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
Проблема изоморфизма для двудольных графов так же вычислительно
трудна, как и известная проблема изоморфизма произвольных конечных графов, для
которой неизвестно полиномиальных алгоритмов. Предлагается полиномиальный генерический алгоритм для проблемы изоморфизма двудольных графов, который дает
правильный ответ на множестве почти всех входов, а на редких оставшихся входах
дает неопределенный ответ.
Cite:
Рыбалов А.Н.
Генерический полиномиальный алгоритм для проблемы изоморфизма двудольных графов
Вестник Омского университета. 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
Dates:
| Submitted: | Apr 29, 2022 |
| Accepted: | Jul 4, 2022 |
| Published online: | Sep 8, 2022 |
| Published print: | Sep 9, 2022 |
Identifiers:
| Elibrary: | 49492553 |
| OpenAlex: | W4403541721 |
Citing:
Пока нет цитирований