17 Дугинов О. И. 2014 2016-05-16 Известия Национальной академии наук Беларуси. Серия физико-математических наук Рассматривается вычислительная сложность двух задач, связанных с бикликами (связными полными двудольными подграфами) графа в классе расщепляемых графов. Для заданного графа и натурального числа k, в задаче о бикликовом покрытии требуется ответить на вопрос: можно ли множество ребер графа покрыть не более k бикликами; в задаче о бикликовом покрытии вершин требуется ответить на вопрос: можно ли множество вершин графа покрыть не более k бикликами. Известно, что обе задачи являются NP-полными для двудольных графов. В работе показано, что обе задачи остаются NP-полными в классе расщепляемых графов. https://www.academjournals.by/publication/13217 https://www.academjournals.by/files/13183