Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/341174| Заглавие документа: | Графы со специальными доминирующими множествами одинаковой мощности |
| Другое заглавие: | Graphs with special dominating sets of the same cardinality / Yu. L. Orlovich, M. A. Shutro |
| Авторы: | Орлович, Ю. Л. Шутро, Н. А. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2025 |
| Издатель: | Минск : БГУ |
| Библиографическое описание источника: | Информационные системы и технологии = Information Systems and Technologies : материалы XI Междунар. науч. конгр. по информатике (CSIST-2025), Респ. Беларусь, Минск, 29–31 окт. 2025 г. В 2 ч. Ч. 2 / Белорус. гос. ун-т ; редкол.: С. В. Абламейко (гл. ред.) [и др]. – Минск : БГУ, 2025. – С. 286-295. |
| Аннотация: | В работе рассматриваются хорошо vе-укрытые графы – графы, в которых все независимые минимальные ve-доминирующие множества имеют одинаковую мощность, а также хорошо ev-укрытые графы – графы, в которых все независимые минимальные ev-доминирующие множества имеют одинаковую мощность. Показано, что задачи распознавания таких графов являются co-NP-полными, в том числе при дополнительных ограничениях на входной граф. Охарактеризованы в терминах запрещённых порождённых подграфов максимальные наследственные подклассы данных классов графов |
| Аннотация (на другом языке): | In the paper, well ve-coverd graphs, that is graphs in which all independent minimal ve-dominating sets have the same cardinality, and well ev-coverd graphs, that is graphs in which all independent minimal ev-dominating sets have the same cardinality, are considered. It is shown that problems of recognizing such graphs are co-NP-complete even under additional constraints on the input graph. The maximal hereditary subclasses of these graph classes are characterized in terms of forbidden induced subgraphs |
| Доп. сведения: | Раздел III. Теоретическая информатика и программная инженерия |
| URI документа: | https://elib.bsu.by/handle/123456789/341174 |
| ISBN: | 978-985-881-851-7 978-985-881-853-1 (ч. 2) |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | 2025. Информационные системы и технологии |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 286-295.pdf | 676,87 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.