Генерическая NP-полнота проблемы распознавания полугамильтоновых графов | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

Вестник Омского университета
ISSN: 1812-3996

Вых. Данные

Год: 2026, Том: 31, Номер: 3, Страницы: 33-41 Страниц : 9 DOI: 10.24147/1812-3996.2026.3.33-41

Ключевые слова

генерическая сложность, NP-полнота, полугамильтоновы графы

Авторы

Рыбалов А.Н. ¹

Организации

1	Институт математики им. С. Л. Соболева СО РАН, Омский филиал, г. Омск, Россия

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

Российский научный фонд

25-11-20023

В статье доказывается генерическая NP-полнота проблемы распознавания полугамильтоновых графов. В рамках генерического подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов.

Рыбалов А.Н.
Генерическая NP-полнота проблемы распознавания полугамильтоновых графов
Вестник Омского университета. 2026. Т.31. №3. С.33-41. DOI: 10.24147/1812-3996.2026.3.33-41 РИНЦ OpenAlex

Поступила в редакцию:	6 июл. 2026 г.
Принята к публикации:	31 июл. 2026 г.
Опубликована в печати:	1 окт. 2026 г.
Опубликована online:	1 окт. 2026 г.

≡ РИНЦ:	93432063
≡ OpenAlex:	W7224099305