Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/265475
Заглавие документа: | On Minimum Maximal Distance-k Matchings |
Авторы: | Kartynnik, Y. Ryzhikov, A. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Кибернетика ЭБ БГУ::ТЕХНИЧЕСКИЕ И ПРИКЛАДНЫЕ НАУКИ. ОТРАСЛИ ЭКОНОМИКИ::Автоматика. Вычислительная техника |
Дата публикации: | 2016 |
Издатель: | Elsevier B.V. |
Библиографическое описание источника: | Electron Notes Discrete Math 2016;56:71-76. |
Аннотация: | We study the computational complexity of several problems connected with the problems of finding a maximal distance-k matching of minimum cardinality or minimum weight. We introduce the class of k-equimatchable graphs which is an edge analogue of k-equipackable graphs. We prove that the recognition of k-equimatchable graphs is co-NP-complete for any fixed k≥2. We also prove that the problem of finding a minimum weight maximal distance-2l matching in chordal graphs is hard to approximate within a factor of εln|V(G)| for a fixed ε unless P=NP. Finally, we show NP-hardness of the minimum maximal induced matching problem in several restricted graph classes. |
URI документа: | https://elib.bsu.by/handle/123456789/265475 |
DOI документа: | 10.1016/j.endm.2016.11.011 |
Scopus идентификатор документа: | 85000766802 |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
1602.04581.pdf | 196,84 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.