О генерической сложности проблемы разбиения графа на треугольники | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2022, Номер: 58, Страницы: 105-111 Страниц : 7 DOI: 10.17223/20710410/58/10

Ключевые слова

генерическая сложность, разбиение графа на треугольники

Авторы

Рыбалов А.Н. ¹

Организации

1	Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия

Информация о финансировании (1)

Российский научный фонд

22-11-20019

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

Рыбалов А.Н.
О генерической сложности проблемы разбиения графа на треугольники
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №58. С.105-111. DOI: 10.17223/20710410/58/10 WOS Scopus РИНЦ OpenAlex

Опубликована в печати:

24 янв. 2023 г.

Web of science:	WOS:000935594100010
Scopus:	2-s2.0-85149693858
РИНЦ:	50123080
OpenAlex:	W4318830427

БД	Цитирований
РИНЦ	1