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