Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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+. 2008 Springer.
