CLUSTERING MINIMUM BICLIQUE COMPLETION OF A BIPARTITE GRAPH
Abstract
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.
About the Authors
O. I. DUGINOV
Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
I. G. KOUZNETSOVA
Belarusian State University, Minsk
Belarus
Belarus
References
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.
Review
Views: 779
Email this article 