danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-194Research ArticleМАТЕМАТИКАMATHEMATICSПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИPOLYNOMIALLY SOLVABLE CASES OF THE MINIMUM BICLIQUE VERTEX-COVER PROBLEMДУГИНОВО. И.DUGINOVO. I.oduginov@gmail.comИнститут математики НАН Беларуси, МинскBelarus201408062016582510Copyright © ДУГИНОВ О.И., 20162016ДУГИНОВ О.И.DUGINOV O.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/194

Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является NP-полной в классе двудольных графов. В данной работе доказано, что эта задача решается за полиномиальное время в классе двудольных перестановочных графов и в классе двудольных дистанционно-наследуемых графов.

The problem of covering the vertex set of a simple graph with a minimum number of complete bipartite subgraphs is studied. It is well known that this problem is NP-complete even for bipartite graphs. This article gives a polynomial time algorithm for solving the considered graph problem when the graph is bipartite permutation or bipartite distance-hereditary.

ReferencesFleischner H., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. P. 2045–2053.Fleischner H., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. P. 2045–2053.Heydari M. H., Morales L., Shields C. O. jr., Sudborough I. H. // Proceedings of 40th Annual Hawaii International Conference on System Sciences. 2007. P. P. 270.Heydari M. H., Morales L., Shields C. O. jr., Sudborough I. H. // Proceedings of 40th Annual Hawaii International Conference on System Sciences. 2007. P. P. 270.Bein D., Morales D., Bein W. et al. // Proceedings of 41th Hawaii International Conference on System Sciences. 2008. P. P. 475.Bein D., Morales D., Bein W. et al. // Proceedings of 41th Hawaii International Conference on System Sciences. 2008. P. P. 475.Zhilin Z., Wang P. // Applied Mechanics and Materials. 2010. Vol. 40–41. P. P. 189–194.Zhilin Z., Wang P. // Applied Mechanics and Materials. 2010. Vol. 40–41. P. P. 189–194.Zhao M. T. // Advanced Materials Research. 2013. Vol. 710. P. 687–691.Zhao M. T. // Advanced Materials Research. 2013. Vol. 710. P. 687–691.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 2008.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 2008.Brandstädt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM. 1999.Brandstädt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM. 1999.Fishburn P., Hammer P. // Discrete Mathematics. 1996. Vol. 160. P. P. 127–148.Fishburn P., Hammer P. // Discrete Mathematics. 1996. Vol. 160. P. P. 127–148.Damaschke P. // Discrete Applied Mathematics. 1992. Vol. 35. P. 67–72.Damaschke P. // Discrete Applied Mathematics. 1992. Vol. 35. P. 67–72.McConnel R., Spinrad J. // Proceedings of the eight annual ACM-SIAM symposium on Discrete algorithms. 1997. P. P. 19–25.McConnel R., Spinrad J. // Proceedings of the eight annual ACM-SIAM symposium on Discrete algorithms. 1997. P. P. 19–25.Gavril F. // SIAM J. on Computing. 1972. Vol. 1. P. 180–187.Gavril F. // SIAM J. on Computing. 1972. Vol. 1. P. 180–187.

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