| Title: | Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3 |
| Other Titles: | Partitioning a split graph into induced subgraphs isomorphic to the path of order 3 |
| Authors: | Дугинов, О. И. |
| Keywords: | публикации ученых;разбиение графа;расщепляемый граф;полиномиальный алгоритм;подграф |
| Issue Date: | 2019 |
| Publisher: | РУП «Издательский дом «Белорусская наука» |
| Citation: | Дугинов, О. И. Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3 / О. И. Дугинов // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2019. – Т. 55, № 1. – С. 32–49. – DOI: https://doi.org/10.29235/1561-2430-2019-55-1-32-49. |
| Abstract: | Установление вычислительной сложности задач на графах является актуальной проблемой. В настоящей работе рассматривается задача, в которой требуется определить, существует ли в заданном 3n-вершинном расщепляемом графе n попарно непересекающихся порожденных подграфов, изоморфных простой цепи порядка 3. Разработан полиномиальный алгоритм, который решает эту задачу. В его основе лежит техника увеличивающих подграфов. Алгоритм может найти применение при решении задач формирования команд. |
| URI: | https://libeldoc.bsuir.by/handle/123456789/37649 |
| Appears in Collections: | Публикации в изданиях Республики Беларусь
|
