ПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВ
Аннотация
Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.
Список литературы
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.
Рецензия
Просмотров: 669
Послать статью по эл. почте 