Skip navigation
Please use this identifier to cite or link to this item: https://libeldoc.bsuir.by/handle/123456789/33741
Title: Покрытие графа несмежными цепями фиксированного порядка
Authors: Дугинов, О. И.
Жиркевич, А. Б.
Keywords: публикации ученых;разбиение графа;полиномиальные алгоритмы;NP-полнота
Issue Date: 2018
Publisher: ОИПИ НАН Беларуси
Citation: Дугинов, О. И. Покрытие графа несмежными цепями фиксированного порядка / О. И. Дугинов, А. Б. Жиркевич // Танаевские чтения : доклады Восьмой Международной Научной конференции, Минск, 27 – 30 марта 2018 г. / ОИПИ НАН Беларуси. — Минск, 2018. — С. 71 – 75.
Abstract: Рассматривается NP-полная задача покрытия графа вершинно-непересекающимися цепями порядка k, k≥3. Установлена NP-полнота задачи в специальных классах графов. Найдены классы графов, для которых задача решается за полиномиальное время. Полученные результаты уточняют границу между NP-полными и полиномиально разрешимыми случаями задачи.
URI: https://libeldoc.bsuir.by/handle/123456789/33741
Appears in Collections:Публикации в изданиях Республики Беларусь

Files in This Item:
File Description SizeFormat 
Duginov_Pokrytiye.pdf253.37 kBAdobe PDFView/Open
Show full item record Google Scholar

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.