RT - article
SR - Electronic
T1 - ПОКРЫТИЕ РАСЩЕПЛЯЕМОГО ГРАФА НАИМЕНЬШИМ ЧИСЛОМ ПОЛНЫХ ДВУДОЛЬНЫХ ПОДГРАФОВ
JF - Известия Национальной академии наук Беларуси. Серия физико-математических наук
SP - 2016-05-16
A1 - Дугинов О. И., 
YR - 2014
UL - https://www.academjournals.by/publication/13217
AB - Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов.