ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ
Анатацыя
Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является NP-полной в классе двудольных графов. В данной работе доказано, что эта задача решается за полиномиальное время в классе двудольных перестановочных графов и в классе двудольных дистанционно-наследуемых графов.
Спіс літаратуры
1. Fleischner H., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. P. 2045–2053.
2. 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.
3. Bein D., Morales D., Bein W. et al. // Proceedings of 41th Hawaii International Conference on System Sciences. 2008. P. P. 475.
4. Zhilin Z., Wang P. // Applied Mechanics and Materials. 2010. Vol. 40–41. P. P. 189–194.
5. Zhao M. T. // Advanced Materials Research. 2013. Vol. 710. P. 687–691.
6. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 2008.
7. Brandstädt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM. 1999.
8. Fishburn P., Hammer P. // Discrete Mathematics. 1996. Vol. 160. P. P. 127–148.
9. Damaschke P. // Discrete Applied Mathematics. 1992. Vol. 35. P. 67–72.
10. McConnel R., Spinrad J. // Proceedings of the eight annual ACM-SIAM symposium on Discrete algorithms. 1997. P. P. 19–25.
11. Gavril F. // SIAM J. on Computing. 1972. Vol. 1. P. 180–187.
##reviewer.review.form##
Праглядаў: 860
Паслаць артыкул па эл. пошце 