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.