Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является NP-трудной в классе P4-свободных двудольных графов и предлагается алгоритм, который решает задачу в классе 2K2-свободных двудольных графов.
ДУГИНОВ О. И., КУЗНЕЦОВА И. Г. ЗАДАЧА МИНИМАЛЬНОГО ПОПОЛНЕНИЯ ДВУДОЛЬНОГО ГРАФА. Доклады Национальной академии наук Беларуси. 2015;59(6):24-32.
1. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.
2. Biclique completion problems for multicast network design / N. Faure [et al.] // Discrete Optimization. – 2007. – Vol. 4. – P. 360–377.
3. Faure, N. Contribution á la resolution de problèmes de regroupement de sessions multicasts: PhD thesis / N. Faure. – Universitè Paris VI, 2006 (in French).
4. Gualandi, S. Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems / S. Gualandi. – Pittsburgh, USA: Springer Berlin Heidelberg, 2009. – P. 87–101.
5. Gualandi, S. A branch-and-price approach to k-clustering minimum biclique completion problem / S. Gualandi, F. Maffioli, C. Magni // International transactions in operational research. – 2013. – Vol. 20. – P. 101–117.
6. Magni, C. Biclique completion problem: models and algorithms: MSc thesis / C. Magni. – Politecnico di Milano, 2009.
7. Gualandi, S. Weighted Biclique Completion via CP-SDP Randomized Rounding / S. Gualandi, F. Malucelli // Proceedings of the European Workshop on Mixed Integer Nonlinear Programming. – Marseille, France, 2010. P. 223–230.
8. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.
9. Babel, L. Recognizing the P4-structure of bipartite graphs / L. Babel, A. Brandstädt, V. B. Le // Discrete Applied Mathematics. – 1999. – Vol. 93. – P. 157–168.
10. Feder, T. Approximating the minimum chain completion problem / T. Feder, H. Mannila, E. Terzi // Information Processing Letters. – 2009. – Vol. 109. – P. 980–985.
11. Heggernes, P. Linear-time certifying recognition algorithms and forbidden induced subgraphs / P. Heggernes, D. Kratsch // Nordic J. of Computing. – 2007. – Vol. 14. – P. 87–108.
