%0 article
%A Дугинов О. И., 
%T ПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВ
%D 2014
%J Известия Национальной академии наук Беларуси. Серия физико-математических наук
%X Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.
%U https://www.academjournals.by/publication/13217