Разбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 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
Рецензия
Просмотров: 1234
Послать статью по эл. почте 