| DC Field | Value | Language |
|---|
| dc.contributor.author | Дугинов, О. И. | - |
| dc.date.accessioned | 2019-12-04T06:58:11Z | - |
| dc.date.available | 2019-12-04T06:58:11Z | - |
| dc.date.issued | 2019 | - |
| dc.identifier.citation | Дугинов, О. И. Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3 / О. И. Дугинов // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2019. – Т. 55, № 1. – С. 32–49. – DOI: https://doi.org/10.29235/1561-2430-2019-55-1-32-49. | ru_RU |
| dc.identifier.uri | https://libeldoc.bsuir.by/handle/123456789/37649 | - |
| dc.description.abstract | Установление вычислительной сложности задач на графах является актуальной проблемой. В настоящей работе рассматривается задача, в которой требуется определить, существует ли в заданном 3n-вершинном расщепляемом графе n попарно непересекающихся порожденных подграфов, изоморфных простой цепи порядка 3. Разработан полиномиальный алгоритм, который решает эту задачу. В его основе лежит техника увеличивающих подграфов. Алгоритм может найти применение при решении задач формирования команд. | ru_RU |
| dc.language.iso | ru | ru_RU |
| dc.publisher | РУП «Издательский дом «Белорусская наука» | ru_RU |
| dc.subject | публикации ученых | ru_RU |
| dc.subject | разбиение графа | ru_RU |
| dc.subject | расщепляемый граф | ru_RU |
| dc.subject | полиномиальный алгоритм | ru_RU |
| dc.subject | подграф | ru_RU |
| dc.title | Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3 | ru_RU |
| dc.title.alternative | Partitioning a split graph into induced subgraphs isomorphic to the path of order 3 | ru_RU |
| dc.type | Статья | ru_RU |
| Appears in Collections: | Публикации в изданиях Республики Беларусь
|
