17 ДУГИНОВ О. И. КУЗНЕЦОВА И. Г. пополнение двудольного графа классы графов вычислительная сложность 2015 2016-06-07 Доклады Национальной академии наук Беларуси Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является NP-трудной в классе P4-свободных двудольных графов и предлагается алгоритм, который решает задачу в классе 2K2-свободных двудольных графов. https://www.academjournals.by/publication/3077 https://www.academjournals.by/files/3059