POLYNOMIALLY SOLVABLE CASES OF THE MINIMUM BICLIQUE VERTEX-COVER PROBLEM
Abstract
The problem of covering the vertex set of a simple graph with a minimum number of complete bipartite subgraphs is studied. It is well known that this problem is NP-complete even for bipartite graphs. This article gives a polynomial time algorithm for solving the considered graph problem when the graph is bipartite permutation or bipartite distance-hereditary.
References
1. Fleischner H., Mujuni E., Paulusma D., Szeider S. // Theoretical Computer Science. 2009. Vol. 410. P. P. 2045–2053.
2. Heydari M. H., Morales L., Shields C. O. jr., Sudborough I. H. // Proceedings of 40th Annual Hawaii International Conference on System Sciences. 2007. P. P. 270.
3. Bein D., Morales D., Bein W. et al. // Proceedings of 41th Hawaii International Conference on System Sciences. 2008. P. P. 475.
4. Zhilin Z., Wang P. // Applied Mechanics and Materials. 2010. Vol. 40–41. P. P. 189–194.
5. Zhao M. T. // Advanced Materials Research. 2013. Vol. 710. P. 687–691.
6. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 2008.
7. Brandstädt A., Le V. B., Spinrad J. Graph classes: a survey. SIAM. 1999.
8. Fishburn P., Hammer P. // Discrete Mathematics. 1996. Vol. 160. P. P. 127–148.
9. Damaschke P. // Discrete Applied Mathematics. 1992. Vol. 35. P. 67–72.
10. McConnel R., Spinrad J. // Proceedings of the eight annual ACM-SIAM symposium on Discrete algorithms. 1997. P. P. 19–25.
11. Gavril F. // SIAM J. on Computing. 1972. Vol. 1. P. 180–187.
Review
Views: 864
Email this article 