Two Points Of The Vertex Cover Problem Solving And Applications

As the density of Very Large-Scale Integration(VLSI) chips increases, the probability of introducing defects on the chips during the fabrication process also increase. A number of reconfiguration strategies have been proposed for increasing the yield of such chips. A typical reconfigurable array consists of a rectangular array plus a set of spare rows (SR) and a set of spare columns (SC).A defective element can be repaired by replacing the row or the column that contains the element with a spare row or a spare column. This problem was first studied by N.Hasan and C.L.Liu in [5],and get some useable result: this problem can be solved as a constraint bipartite vertex cover(CBVC) problem. Hasan and Liu proposed two algorithms that solves the CBVC problem. One is approximate algorithm which is the most efficient algorithm until now. But this algorithm do not guarantee the minimization of the set of vertex cover, which mean while do not guarantee it can be fixed that all of fault chips which should be fixed. Another one is heuristic branch-and-bound algorithm, and this algorithm just work well in moderate size. Che [1] proposed a heuristic fault spectrum algorithm that solves the CBVC problem very efficient but still not guarantee the minimization of the set of vertex cover.Buss[8] developed the first fixed-parameter tractable algorithm of running time O(kn + 2kk2k+2)for the problem, which was later improved toO(kn + 2k k2)by Downey and Fellows[9]. More recently, parameterized algorithm for the vertex cover problem have further drawn researchers' attention, and continuous improvements on the problem have been developed. Balasubramanian [2] first broke the bound 2 barrier in the base of the exponential term and developed an O(kn + 1.322718k k2) time algorithm for the problem. This algorithm was further improved most recently by Chen and Kanj[3] running in O(kn + 1.271kk2) time.But the classical vertex cover algorithm can not use in the CBVC problem directly, because the CBVC problem have more term need to constraint. Another hand, the CBVC problem give our some useful characterized to reduce running time.This paper based on the fixed-parameter computer theory, use some special characterize of bipartite graph, developed a simple but efficient exact algorithm,which running in O(1.26k1+k2 +(k1 + k2)n) time.