Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/341572| Заглавие документа: | NP-полнота задачи о независимом доминирующем множестве в классе кубических планарных двудольных графов |
| Авторы: | Ловеров, Я.Л. Орлович, Ю.Л |
| Цифровой идентификатор автора ORCID: | 0000-0002-6398-8306 |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика |
| Дата публикации: | 2020 |
| Издатель: | Институт математики им. С. Л. Соболева СО РАН |
| Библиографическое описание источника: | Дискретн. анализ и исслед. опер.2020; 27(2): 65–89 |
| Аннотация: | Известно, что как в классе кубических планарных графов, так и в классе кубических двудольных графов задача о независимом доминирующем множестве NP-полна. Вопрос о вычислительной сложности данной задачи в пересечении вышеупомянутых классов является открытым. В настоящей работе доказывается, что в классе кубических планарных двудольных графов задача о независимом доминирующем множестве также NP-полна. |
| URI документа: | https://elib.bsu.by/handle/123456789/341572 |
| DOI документа: | 10.33048/daio.2020.27.657 |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| Орлович.pdf | 403,88 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.