Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/10369
Title: Алгоритм распознавания принадлежности хордального графа классу графов C
Authors: Петрович, Р. А.
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: 2011
Publisher: БГУ
Citation: Международный конгресс по информатике: информационные системы и технологии: материалы международного научного конгресса 31 окт. – 3 нояб. 2011 г. : в 2 ч. Ч. 2. – Минск: БГУ, 2011. – C. 328-333.
Abstract: Граф G называется полярным, если существует такое разбиение его множества вершин VG на части A и B, что все связные компоненты порожденного подграфа G(B) и дополнительного )(AG являются полными графами [1]. Известно, что проблема распознавания полярности – NP-полная [1]. Выходом из сложившейся ситуации является попытка ее решения в более узких классах графов. Граф G принадлежит классу C, если множество VG можно разбить на два подмножества A и B, что порожденный подграф G(A) – пустой, а в G(B) степени вершин равны 0, либо 1 [1]. Однако и задача распознавания принадлежности графа классу C является NP-полной [1]. Поэтому на исходный граф накладывается еще одно ограничение: хордальность. В результате разработан полиномиальный алгоритм распознавания принадлежности хордального графа классу C.
Description: Секция 10. Теоретическая информатика
URI: http://elib.bsu.by/handle/123456789/10369
ISBN: 978-985-518-564-3
Appears in Collections:2011. Международный конгресс по информатике : информационные системы и технологии. Часть 2.

Files in This Item:
File Description SizeFormat 
71 ПЕТРОВИЧ.pdf335,36 kBAdobe PDFView/Open


PlumX

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