TY  - JOUR
T1  - ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ
JF  - Доклады Национальной академии наук Беларуси
AU  - ДУГИНОВ О. И., 
Y1  - 2016-06-08
UR  - https://www.academjournals.by/publication/3114
N2  - Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является NP-полной в классе двудольных графов. В данной работе доказано, что эта задача решается за полиномиальное время в классе двудольных перестановочных графов и в классе двудольных дистанционно-наследуемых графов.