The generic complexity of the graph triangulation problem

Jazyk:	ruština
Rok vydání:	2022
Předmět:	графы разбиение графа на треугольники генерическая сложность
Zdroj:	Прикладная дискретная математика. 2022. № 58. С. 105-111
Popis:	NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=od______3810::78bd128466b5f0a08e8f021da6c65bf7 https://vital.lib.tsu.ru/vital/access/manager/Repository/koha:000925354 Zobrazit plný text záznamu