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: | Публикации в изданиях Республики Беларусь |
File | Description | Size | Format | |
---|---|---|---|---|
Duginov_Pokrytiye.pdf | 253.37 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.