Partitioning a split graph into induced subgraphs isomorphic to the path of order 3.
https://doi.org/10.29235/1561-2430-2019-55-1-32-49
Abstract
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.
About the Author
O. I. Duginov
Belarusian State University.
Russian Federation
Russian Federation
Ph. D. (Physics and Mathematics), Assistant Professor of Department of Discrete Mathematics and Algorithmics.
4, Nezavisimosti Ave., 220030. Minsk.
References
1. 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).
2. Dyer 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-3
3. Brandstädt A., Le V. B., Spinrad J. P. Graph Classes: A Survey. Philadelphia, SIAM, 1999. 306 p. https://doi.org/10.1137/1.9780898719796
4. Monnot 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
5. Lovàsz L., Plummer M. Matching Theory. AMS Chelsea Publishing, 2009. 543 p. https://doi.org/10.1090/chel/367
6. Bevern 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
Review
Views: 1231
Email this article 