Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/341911| Заглавие документа: | NP-Completeness of the Independent Dominating Set Problem in the Class of Cubic Planar Bipartite Graphs |
| Авторы: | Loverov, Y.A. Orlovich, Y.L. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2020 |
| Издатель: | Мн: Институт математики НАН Беларуси |
| Библиографическое описание источника: | Journal of Applied and Industrial Mathematics. 2020;Vol. 14(2):P. 353-368 |
| Аннотация: | It is known that the independent dominating set problem is NP-complete both in the classof cubic planar graphs and in the class of cubic bipartite graphs. Still open is the question aboutthe computational complexity of the problem in the intersection of these graph classes. In thisarticle, we prove that the independent dominating set problem is NP-complete in the class ofcubic planar bipartite graphs |
| URI документа: | https://elib.bsu.by/handle/123456789/341911 |
| DOI документа: | 10.1134/S1990478920020131. |
| Лицензия: | info:eu-repo/semantics/openAccess |
| Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| Орлович1.pdf | 1,14 MB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.