Сложность задачи о наибольшем независимом множестве в классе  треугольных графов

Орлович, Ю. Л.; Блажевич, Я.; Гордон, В. С.; Долгий, А. Б.; Финке, Г.

Issue Date Author Title Subject

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/10368

Title:	Сложность задачи о наибольшем независимом множестве в классе треугольных графов
Authors:	Орлович, Ю. Л. Блажевич, Я. Гордон, В. С. Долгий, А. Б. Финке, Г.
Keywords:	ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date:	2011
Publisher:	БГУ
Citation:	Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 323-328.
Abstract:	Рассматриваются вопросы вычислительной сложности и сложности аппро-кимации задачи о наибольшем независимом множестве в классе треугольных графов. Вводится новый теоретико-графовый параметр – верхнее окрестностное число независимости – и связанная с ним задача распознавания (задача о верхнем окрестностном независимом множестве). Показано, что значение этого параметра для треугольного графа равно числу независимости. Установлено, что обе рассматриваемые задачи являются NP-полными в классе треугольных графов и не аппроксимируются за полиномиальное время с точностью до произвольной константы K > 1 (при условии P ≠ NP). Найдены также некоторые полиномиально разрешимые случаи этих задач для треугольных графов.
Description:	Секция 10. Теоретическая информатика
URI:	http://elib.bsu.by/handle/123456789/10368
ISBN:	978-985-518-564-3
Appears in Collections:	2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2. Статьи факультета прикладной математики и информатики

Files in This Item:

File	Description	Size	Format
70 ОРЛОВИЧ.pdf		361,42 kB	Adobe PDF	View/Open

Show full item record Google Scholar