@article{Дугинов О. И.2016-05-16,
author = { Дугинов О. И.},
title = {ПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВ},
year = {2014},
publisher = {NP «NEICON»},
abstract = {Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.},
URL = {https://www.academjournals.by/publication/13217},
eprint = {https://www.academjournals.by/files/13183},
journal = {Известия Национальной академии наук Беларуси. Серия физико-математических наук},
}