ЗАДАЧА МИНИМАЛЬНОГО ПОПОЛНЕНИЯ ДВУДОЛЬНОГО ГРАФА
Аннотация
Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является NP-трудной в классе P4-свободных двудольных графов и предлагается алгоритм, который решает задачу в классе 2K2-свободных двудольных графов.
Об авторах
О. И. ДУГИНОВ
Институт математики НАН Беларуси, Минск
Беларусь
Беларусь
И. Г. КУЗНЕЦОВА
Белорусский государственный университет, Минск
Беларусь
Беларусь
Список литературы
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.
Рецензия
Просмотров: 734
Послать статью по эл. почте 