О генерической сложности проблемы разбиения графа на треугольники А. Н. Рыбалов
Material type: ArticleContent type: Текст Media type: электронный Other title: The generic complexity of the graph triangulation problem [Parallel title]Subject(s): генерическая сложность | графы | разбиение графа на треугольникиGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 58. С. 105-111Abstract: NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.Библиогр.: 13 назв.
NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.
There are no comments on this title.