Scientific Library of Tomsk State University

   E-catalog        

Image from Google Jackets
Normal view MARC view

О генерической сложности проблемы разбиения графа на треугольники А. Н. Рыбалов

By: Рыбалов, Александр НиколаевичMaterial type: ArticleArticleContent 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 для её решения не существует полиномиального сильно генерического алгоритма.
Tags from this library: No tags from this library for this title. Log in to add tags.
No physical items for this record

Библиогр.: 13 назв.

NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.

There are no comments on this title.

to post a comment.