О генерической сложности проблемы разбиения графа на треугольники Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2022, Number: 58, Pages: 105-111 Pages count : 7 DOI: 10.17223/20710410/58/10 | ||
| Tags | генерическая сложность, разбиение графа на треугольники | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 22-11-20019 |
Abstract:
NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.
Cite:
Рыбалов А.Н.
О генерической сложности проблемы разбиения графа на треугольники
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №58. С.105-111. DOI: 10.17223/20710410/58/10 WOS Scopus РИНЦ OpenAlex
О генерической сложности проблемы разбиения графа на треугольники
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №58. С.105-111. DOI: 10.17223/20710410/58/10 WOS Scopus РИНЦ OpenAlex
Dates:
| Published print: | Jan 24, 2023 |
Identifiers:
| Web of science: | WOS:000935594100010 |
| Scopus: | 2-s2.0-85149693858 |
| Elibrary: | 50123080 |
| OpenAlex: | W4318830427 |
Citing:
| DB | Citing |
|---|---|
| Elibrary | 1 |