Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

ЗАДАЧА МИНИМАЛЬНОГО ПОПОЛНЕНИЯ ДВУДОЛЬНОГО ГРАФА

Аннотация

Рассматривается графовая задача, в которой задан двудольный граф с выделенной долей и требуется добавить в граф наименьшее число дополнительных ребер так, что множество вершин выделенной доли получившегося графа можно разбить на заданное число непустых множеств, каждое из которых содержит только вершины с одинаковыми окружениями. В работе установлено, что задача является 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.


Рецензия

Просмотров: 727


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)