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