Доступ открыт Открытый доступ  Доступ закрыт Только для подписчиков

Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3


https://doi.org/10.29235/1561-2430-2019-55-1-32-49

Полный текст:


Аннотация

Установление вычислительной сложности задач на графах является актуальной проблемой. В настоящей работе рассматривается задача, в которой требуется определить, существует ли в заданном 3n-вершинном расщепляемом графе n попарно непересекающихся порожденных подграфов, изоморфных простой цепи порядка 3. Разработан полиномиальный алгоритм, который решает эту задачу. В его основе лежит техника увеличивающих подграфов. Алгоритм может найти применение при решении задач формирования команд.

Об авторе

О. И. Дугинов
Белорусский государственный университет.
Россия

Кандидат физико-математических наук, доцент кафедры дискретной математики и алгоритмики.

пр. Независимости, 4, 220030, г. Минск.



Список литературы

1. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Ленанд, 2017. – 390 с.

2. Dyer, M. E. On the complexity of partitioning graphs into connected subgraphs / M.E. Dyer, A. M. Frieze // Discrete Applied Mathematics. – 1985. – Vol. 10, № 2. – P. 139–153. https://doi.org/10.1016/0166-218x(85)90008-3

3. Brandstädt, A. Graph Classes: A Survey / A. Brandstädt, V. B. Le, J. P. Spinrad. – Philadelphia: SIAM, 1999. – 306 p. https://doi.org/10.1137/1.9780898719796

4. Monnot, J. The path partition problem and related problems in bipartite graphs / M. Monnot, S. Toulouse // Operations Research Letters. – 2007. – Vol. 35, № 5. – P. 677–684. https://doi.org/10.1016/j.orl.2006.12.004

5. Ловас, Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М.: Мир, 1998. – 656 с.

6. Partitioning Perfect Graphs into Stars / R. van Bevern [et. al.] // J. Graph Theory. – 2016. – Vol. 85, № 2. – P. 297-335. https://doi.org/10.1002/jgt.22062


Дополнительные файлы

Просмотров: 133

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)