Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/160655
Заглавие документа: | Connected-domination triangle graphs, perfect connected-neighbourhood graphs and connected neighbourhood sets |
Авторы: | Kartynnik, Y. A. Orlovich, Y. L. |
Тема: | ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика |
Дата публикации: | 25-окт-2016 |
Издатель: | Минск: БГУ |
Аннотация: | We introduce and characterize the class of graphs in which every connected dominating set is a (connected) neighbourhood set and the class of graphs whose all connected induced subgraphs have equal minimum neighbourhood set and minimum connected neighbourhood set cardinalities. Assuming P - NP, we also prove that the minimum connected neighbourhood set problem cannot be approximated within a logarithmic factor in polynomial time in their common subclass, the class of simplicial split graphs. |
URI документа: | http://elib.bsu.by/handle/123456789/160655 |
ISBN: | 978-985-566-369-1 |
Располагается в коллекциях: | Секция 12. ТЕОРЕТИЧЕСКАЯ ИНФОРМАТИКА |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
Kartynnik_Orlovich.pdf | 353,76 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.