@article{ДУГИНОВ О. И.2016-06-07,
author = { ДУГИНОВ О. И.,  КУЗНЕЦОВА И. Г.},
title = {ЗАДАЧА МИНИМАЛЬНОГО ПОПОЛНЕНИЯ ДВУДОЛЬНОГО ГРАФА},
year = {2015},
publisher = {NP «NEICON»},
abstract = {Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является NP-трудной в классе P4-свободных двудольных графов и предлагается алгоритм, который решает задачу в классе 2K2-свободных двудольных графов.},
URL = {https://www.academjournals.by/publication/3077},
eprint = {https://www.academjournals.by/files/3059},
journal = {Доклады Национальной академии наук Беларуси},
}