Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

Springer Science and Business Media LLC - Tập 23 - Trang 763-768 - 2008
Jian-Xin Wang1, Xiao-Shuang Xu1, Jian-Er Chen1,2
1School of Information Science and Engineering, Central South University, Changsha, China
2Department of Computer Science, Texas A&M University, College Station, U.S.A.

Tóm tắt

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ɛ > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (k u , k l ), our algorithm constructs a vertex cover of size (k * u , k * l ), satisfying max {k * u /k u , k * l /k l } ≤ 1 + ɛ.

Tài liệu tham khảo

Chen J, Kanj I A. Constrained minimum vertex cover in bipartite graphs: Complexity and parameterized algorithms. Journal of Computer and System Science, 2003, 67(4): 833–847. Hasan N, Liu C L. Minimum fault coverage in reconfigurable arrays. In Proc. 18th Int. Symp. Fault-Tolerant Computing (FTCS’88), Los Alamitos, CA, 1988, pp.348–353. Nilsson N J. Principles of Artificial Intelligence. Palo Alto: Tioga Publishing Co., CA, 1980. Blough D M. On the reconfigurable of memory arrays containing clustered faults. In Proc. 21st Int. Symp. Fault-Tolerant Computing (FTCS’91), Montreal, Canada, 1991, pp.444–451. Blough D M, Pelc A. Complexity of fault diagnosis in comparison models. IEEE Trans. Comput., 1992, 41(3): 318–323. Hasan N, Liu C L. Fault covers in reconfigurable PLAs. In Proc. 20th Int. Symp. Fault-Tolerant Computing (FTCS’90), Newcastle upon Tyne, 1990, pp.166–173. Kuo S Y, Fuchs W K. Efficient spare allocation for reconfigurable arrays. IEEE Des. Test, 1987, 4(1): 24–31. Low C P, Leong H W. A new class of efficient algorithms for reconfiguration of memory arrays. IEEE Trans. Comput., 1996, 45(1): 614–618. Smith M D, Mazumder P. Generation of minimal vertex cover for row/column allocation in self-repairable arrays. IEEE Trans. Comput., 1996, 45(1): 109–115. Fernau H, Niedermeier R. An efficient exact algorithm for constraint bipartite vertex cover. J. Algorithms, 2001, 38(2): 374–410. Downey R, Fellows M. Parameterized Complexity. Berlin: Springer, 1999. Cormen T H, Leiserson C E, Rovest R L. Introduction to Algorithms. New York: McGraw-Hill Book Company, 1992. Lovasz L, Plummer M D. Matching Theory. Amsterdam: North-Holland, 1986.