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

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы разбиения графа на треугольники	644 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/58/10

Title: О генерической сложности проблемы разбиения графа на треугольники
Title: The generic complexity of the graph triangulation problem
Creator: Рыбалов, Александр Николаевич
Date: 2022
DOI: 10.17223/20710410/58/10
Description: NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P 6= NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.

Created: 09-12-2022

243 Visitors

145 Hits

102 Downloads

Журналы ТГУ О генерической сложности проблемы разбиения графа на треугольники