ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ
Аннотация
Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является 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.
Рецензия
Просмотров: 858
Послать статью по эл. почте 