Logo BSU

  1. Электронная библиотека БГУ
  2. Факультет прикладной математики и информатики
  3. НАУЧНЫЕ ПУБЛИКАЦИИ ФАКУЛЬТЕТА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
  4. Материалы конференций факультета прикладной математики и информатики
  5. Информационные системы и технологии (IST).
  6. 2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.
Issue Date Author Title Subject
Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/10368
Full metadata record
DC FieldValueLanguage
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
Appears in Collections:2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.
Статьи факультета прикладной математики и информатики

Files in This Item:
File Description SizeFormat 
70 ОРЛОВИЧ.pdf361,42 kBAdobe PDFView/Open
Show simple item record Google Scholar



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.