Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/10368| Заглавие документа: | Сложность задачи о наибольшем независимом множестве в классе треугольных графов |
| Авторы: | Орлович, Ю. Л. Блажевич, Я. Гордон, В. С. Долгий, А. Б. Финке, Г. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2011 |
| Издатель: | БГУ |
| Библиографическое описание источника: | Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 323-328. |
| Аннотация: | Рассматриваются вопросы вычислительной сложности и сложности аппро-кимации задачи о наибольшем независимом множестве в классе треугольных графов. Вводится новый теоретико-графовый параметр – верхнее окрестностное число независимости – и связанная с ним задача распознавания (задача о верхнем окрестностном независимом множестве). Показано, что значение этого параметра для треугольного графа равно числу независимости. Установлено, что обе рассматриваемые задачи являются NP-полными в классе треугольных графов и не аппроксимируются за полиномиальное время с точностью до произвольной константы K > 1 (при условии P ≠ NP). Найдены также некоторые полиномиально разрешимые случаи этих задач для треугольных графов. |
| Доп. сведения: | Секция 10. Теоретическая информатика |
| URI документа: | http://elib.bsu.by/handle/123456789/10368 |
| ISBN: | 978-985-518-564-3 |
| Располагается в коллекциях: | 2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2. Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 70 ОРЛОВИЧ.pdf | 361,42 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.