Logo BSU

  1. Электронная библиотека БГУ
  2. Факультет прикладной математики и информатики
  3. НАУЧНЫЕ ПУБЛИКАЦИИ ФАКУЛЬТЕТА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
  4. Материалы конференций факультета прикладной математики и информатики
  5. Информационные системы и технологии (IST).
  6. 2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.
Даты публикации Авторы Заглавия Темы
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/10368
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorОрлович, Ю. Л.-
dc.contributor.authorБлажевич, Я.-
dc.contributor.authorГордон, В. С.-
dc.contributor.authorДолгий, А. Б.-
dc.contributor.authorФинке, Г.-
dc.date.accessioned2012-05-30T08:17:17Z-
dc.date.available2012-05-30T08:17:17Z-
dc.date.issued2011-
dc.identifier.citationМеждународный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 323-328.ru
dc.identifier.isbn978-985-518-564-3-
dc.identifier.urihttp://elib.bsu.by/handle/123456789/10368-
dc.descriptionСекция 10. Теоретическая информатикаru
dc.description.abstractРассматриваются вопросы вычислительной сложности и сложности аппро-кимации задачи о наибольшем независимом множестве в классе треугольных графов. Вводится новый теоретико-графовый параметр – верхнее окрестностное число независимости – и связанная с ним задача распознавания (задача о верхнем окрестностном независимом множестве). Показано, что значение этого параметра для треугольного графа равно числу независимости. Установлено, что обе рассматриваемые задачи являются NP-полными в классе треугольных графов и не аппроксимируются за полиномиальное время с точностью до произвольной константы K > 1 (при условии P ≠ NP). Найдены также некоторые полиномиально разрешимые случаи этих задач для треугольных графов.ru
dc.language.isoruru
dc.publisherБГУru
dc.subjectЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математикаru
dc.titleСложность задачи о наибольшем независимом множестве в классе треугольных графовru
dc.typeArticleru
Располагается в коллекциях:2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.
Статьи факультета прикладной математики и информатики

Полный текст документа:
Файл Описание РазмерФормат 
70 ОРЛОВИЧ.pdf361,42 kBAdobe PDFОткрыть
Показать базовое описание документа Статистика Google Scholar



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.