Генерическая NP-полнота проблемы распознавания полугамильтоновых графов Full article
| Journal |
Вестник Омского университета
ISSN: 1812-3996 |
||
|---|---|---|---|
| Output data | Year: 2026, Volume: 31, Number: 3, Pages: 33-41 Pages count : 9 DOI: 10.24147/1812-3996.2026.3.33-41 | ||
| Tags | генерическая сложность, NP-полнота, полугамильтоновы графы | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
В статье доказывается генерическая NP-полнота проблемы распознавания полугамильтоновых графов. В рамках генерического подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов.
Cite:
Рыбалов А.Н.
Генерическая NP-полнота проблемы распознавания полугамильтоновых графов
Вестник Омского университета. 2026. Т.31. №3. С.33-41. DOI: 10.24147/1812-3996.2026.3.33-41 РИНЦ OpenAlex
Генерическая NP-полнота проблемы распознавания полугамильтоновых графов
Вестник Омского университета. 2026. Т.31. №3. С.33-41. DOI: 10.24147/1812-3996.2026.3.33-41 РИНЦ OpenAlex
Dates:
| Submitted: | Jul 6, 2026 |
| Accepted: | Jul 31, 2026 |
| Published print: | Oct 1, 2026 |
| Published online: | Oct 1, 2026 |
Identifiers:
| ≡ Elibrary: | 93432063 |
| ≡ OpenAlex: | W7224099305 |