TY  - SER
AU  - Рыбалов,Александр Николаевич
TI  - О генерической сложности проблемы разбиения графа на треугольники
KW  - генерическая сложность
KW  - графы
KW  - разбиение графа на треугольники
KW  - статьи в журналах
N1  - Библиогр.: 13 назв
N2  - NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма
UR  - http://vital.lib.tsu.ru/vital/access/manager/Repository/koha:000925354
ER  -