Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ

Полный текст:

Аннотация

Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является 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.


Просмотров: 258


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)