ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ
2014
Задача покрытия множества вершин графа наименьшим числом полных двудольных подграфов является NP-полной в классе двудольных графов. В данной работе доказано, что эта задача решается за полиномиальное время в классе двудольных перестановочных графов и в классе двудольных дистанционно-наследуемых графов.
ДУГИНОВ О. И. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ СЛУЧАИ ЗАДАЧИ О НАИМЕНЬШЕМ ПОКРЫТИИ ВЕРШИН ГРАФА БИКЛИКАМИ. Доклады Национальной академии наук Беларуси. 2014;58(2):5-10.
Цитирование
Список литературы