Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3
https://doi.org/10.29235/1561-2430-2019-55-1-32-49
Анатацыя
Установление вычислительной сложности задач на графах является актуальной проблемой. В настоящей работе рассматривается задача, в которой требуется определить, существует ли в заданном 3n-вершинном расщепляемом графе n попарно непересекающихся порожденных подграфов, изоморфных простой цепи порядка 3. Разработан полиномиальный алгоритм, который решает эту задачу. В его основе лежит техника увеличивающих подграфов. Алгоритм может найти применение при решении задач формирования команд.
Аб аўтары
О. Дугинов
Белорусский государственный университет.
Расія
Спіс літаратуры
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
Праглядаў:
1364
Паслаць артыкул па эл. пошце 