danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-157Research ArticleМАТЕМАТИКАMATHEMATICSЗАДАЧА МИНИМАЛЬНОГО ПОПОЛНЕНИЯ ДВУДОЛЬНОГО ГРАФАCLUSTERING MINIMUM BICLIQUE COMPLETION OF A BIPARTITE GRAPHДУГИНОВО. И.DUGINOVO. I.oduginov@gmail.comКУЗНЕЦОВАИ. Г.KOUZNETSOVAI. G.irene.kuzn@gmail.comИнститут математики НАН Беларуси, МинскБеларусьInstitute of Mathematics of the National Academy of Sciences of Belarus, MinskBelarusБелорусский государственный университет, МинскБеларусьBelarusian State University, MinskBelarus2015070620165962432Copyright © ДУГИНОВ О.И., КУЗНЕЦОВА И.Г., 20162016ДУГИНОВ О.И., КУЗНЕЦОВА И.Г.DUGINOV O.I., KOUZNETSOVA I.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/157

Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является NP-трудной в классе P4-свободных двудольных графов и предлагается алгоритм, который решает задачу в классе 2K2-свободных двудольных графов.

In this article we show that the clustering minimum biclique completion problem is NP-complete in the class of P4-free bipartite graphs. We have also proposed a dynamic programming algorithm for that problem restricted to 2K2-free bipartite graphs.

пополнение двудольного графаклассы графоввычислительная сложностьclustering minimum biclique completion problemgraph classescomputational complexityReferencesЛекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.Biclique completion problems for multicast network design / N. Faure [et al.] // Discrete Optimization. – 2007. – Vol. 4. – P. 360–377.Biclique completion problems for multicast network design / N. Faure [et al.] // Discrete Optimization. – 2007. – Vol. 4. – P. 360–377.Faure, N. Contribution á la resolution de problèmes de regroupement de sessions multicasts: PhD thesis / N. Faure. – Universitè Paris VI, 2006 (in French).Faure, N. Contribution á la resolution de problèmes de regroupement de sessions multicasts: PhD thesis / N. Faure. – Universitè Paris VI, 2006 (in French).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.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.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.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.Magni, C. Biclique completion problem: models and algorithms: MSc thesis / C. Magni. – Politecnico di Milano, 2009.Magni, C. Biclique completion problem: models and algorithms: MSc thesis / C. Magni. – Politecnico di Milano, 2009.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.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.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.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.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.Feder, T. Approximating the minimum chain completion problem / T. Feder, H. Mannila, E. Terzi // Information Processing Letters. – 2009. – Vol. 109. – P. 980–985.Feder, T. Approximating the minimum chain completion problem / T. Feder, H. Mannila, E. Terzi // Information Processing Letters. – 2009. – Vol. 109. – P. 980–985.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.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.

The authors declare that there are no conflicts of interest present.