vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2019-55-1-32-49vestifm-364Research ArticleМАТЕМАТИКАMATHEMATICSРазбиение расщепляемого графа на порожденные подграфы, изоморфные цепи порядка 3Partitioning a split graph into induced subgraphs isomorphic to the path of order 3.ДугиновО. И.DuginovO. I.

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

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

 Ph. D. (Physics and Mathematics), Assistant Professor of Department of Discrete Mathematics and Algorithmics.

4, Nezavisimosti Ave., 220030. Minsk.

duginov@bsu.byБелорусский государственный университет.Belarusian State University.2019250320195513249Copyright © Дугинов О.И., 20192019Дугинов О.И.Duginov O.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/364

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

The study of the computational complexity of problems on graphs is an urgent problem. We show that the problem of deciding whether the vertex set of a given split graph of order 3n can be partitioned into induced subgraphs isomorphic to P3 is a polynomially solvable problem. We develop a polynomial-time algorithm based on the method of augmenting graphs. The developed efficient algorithm can be used for solving team formation problems.

разбиение графа на специальные подграфырасщепляемый графполиномиальный алгоритмpartitioning a graph into certain subgraphssplit graphpolynomial-time algorithmReferencesЛекции по теории графов / В. А. Емеличев [и др.]. – М.: Ленанд, 2017. – 390 с.Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on Graph Theory. Moscow, Lenand Publ., 2017. 390 p. (in Russian).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-3Dyer M. E., Frieze A. M. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 1985, vol. 10, no. 2, pp. 139–153. https://doi.org/10.1016/0166-218x(85)90008-3Brandstä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.9780898719796Brandstädt A., Le V. B., Spinrad J. P. Graph Classes: A Survey. Philadelphia, SIAM, 1999. 306 p. https://doi.org/10.1137/1.9780898719796Monnot, 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.004Monnot J., Toulouse S. The path partition problem and related problems in bipartite graphs. Operations Research Letters, 2007, vol. 35, no. 5, pp. 677–684. https://doi.org/10.1016/j.orl.2006.12.004Ловас, Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М.: Мир, 1998. – 656 с.Lovàsz L., Plummer M. Matching Theory. AMS Chelsea Publishing, 2009. 543 p. https://doi.org/10.1090/chel/367Partitioning 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.22062Bevern van R., Bredereck R., Bulteau L., Chen J., Froese V., Niedermeier R., Woeginger G. J. Partitioning Perfect Graphs into Stars. Journal of Graph Theory, 2016, vol. 85, no. 2, pp. 297–335. https://doi.org/10.1002/jgt.22062

The authors declare that there are no conflicts of interest present.