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

Дугинов О. И.

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

Дугинов О. И.

2014

Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.

Дугинов О. И. ПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВ. Известия Национальной академии наук Беларуси. Серия физико-математических наук. 2014;(1):54-60.

Цитирование

Список литературы

1. ЕмеличевВ. А., Мельников О. И., СарвановВ. И., Тышкевич Р. А. Лекции по теории графов. М., 2011.

2. Brandstadt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM Monographs on Discrete Math. and Applications, 1999. P. 306.

3. FleischnerH., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. 2045-2053.

4. Amiliastre J., Vilarem M., Janssen P. // Discrete Applied Mathematics. 1998. Vol. 86. P. 125-144.

5. CornazD., Fonplut J. // Discrete Mathematics. 2006. Vol. 306. P. 495-507.

6. Chakrabarti D., Papadimitriou S., Modha D. S., Faloutsos C. // Proceedings of the 10th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’04). [S. l.], 2004. P. 79-88.

7. Heydari M. H., Morales L., Shields C. O, Sudborough I. H. // Proceedings of the 40th Annual Hawaii International Conference on System Sciences (HICSS’07). [S. l.], 2007. P. 270b.

8. Fоldes S., Hammer P. // Congressus Numerantium. 1977. Vol. 19. P. 311-315.

9. Тышкевич Р. И., Черняк А. А. // Изв. АН БССР. Сер. физ.-мат. наук. 1979. Т. 5. С. 14-26.

10. Orlin, J. // Indagationes Mathematicae. 1977. Vol. 80. P. 406-424.

11. MullerH. // Discrete Mathematics. 1996. Vol. 149. P. 159-187.

12. Lubiw A. // SIAM J. on Discrete Mathematics. 1990. Vol. 3. P. 98-115.

13. Soto J., Telha C. // Proceedings of the 15th International Conference on Integer programming and combinatoral optimization.). [S. l.], 2011. P. 389-403.

14. Лепин В. В. // Тр. Ин-та математики. 2010. Т. 18. С. 60-78.

15. Лепин В. В., Дугинов О. И. // Тр. Ин-та математики. Т. 19. С. 69-81.

16. Fishburn P. C., Hammer P. L. // Discrete Mathematics. 1996. Vol. 160. P. 127-148.

17. Weihe K. // Proceedings of the 1st Conference on Algorithms and Experiments (ALEX-1998). [S. l.], 1998. P. 1-8.

18. Kratzke T., ReznickB., WestD. // Transactions of the American mathematical society. 1988. Vol. 308. P. 637-653.

19. Дугинов О. И., Лепин В. В. // Веб-программирование и Интернет-технологии WebConf2012: материалы 2-й Междунар. науч.-практ. конф., БГУ Минск, 2012.

Источник

Информация

Автор

Дугинов О. И. Институт математики Национальной академии наук Беларуси, Минск

Страницы

54-60

Год издания

2014

Коллекции

Известия Национальной академии наук Беларуси. Серия физико-математических наук