Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
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.